# BZOJ1509: [NOI2003]逃学的小孩(树的直径)

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 1126  Solved: 567

[Submit][Status][Discuss]

## Sample Input

4 3 1 2 1 2 3 1 3 4 1

4

## Source

```#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
const int INF = 1e9 + 10, MAXN = 1e6 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
struct Edge {
int u, v, w, nxt;
}E[MAXN];
inline void AddEdge(int x, int y, int z) {
E[num] = (Edge) {x, y, z, head[x]};
}
int dis[MAXN], mx, mxdis;
void dfs(int x, int fa) {
for(int i = head[x]; i != -1; i = E[i].nxt) {
if(E[i].v == fa) continue;
dis[E[i].v] = dis[x] + E[i].w;
dfs(E[i].v, x);
if(dis[E[i].v] > mxdis) mxdis = dis[E[i].v], mx = E[i].v;
}
}
int Node1, Node2, dis1[MAXN], dis2[MAXN];
int GetAns() {
memset(dis, 0, sizeof(dis)); dfs(Node1, 0);
for(int i = 1; i <= N; i++) dis1[i] = dis[i];
memset(dis, 0, sizeof(dis)); dfs(Node2, 0);
for(int i = 1; i <= N; i++) dis2[i] = dis[i];
int rt = 0;
for(int i = 1; i <= N; i++)
rt = max(rt, min(dis1[i], dis2[i]));
return rt;
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
for(int i = 1; i <= M; i++) {
}
dfs(1, 0); Node1 = mx;
memset(dis, 0, sizeof(dis)); mxdis = 0;
dfs(mx, 0); Node2 = mx;
int ans = dis[mx];
printf("%I64d", ans + GetAns());
}```

1811 篇文章125 人订阅

0 条评论

## 相关文章

39790

25440

### 1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

29360

### ClassPathXmlApplicationContext方式读取配置文件

public interface BeanFactory {   public Object getBean(String id); }   //实现类Clas...

22450

245100

### 2243: [SDOI2011]染色

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

32490

1K80

37910

11020

9120