[lg3304][SDOI2013]直径

题目大意:

给定一棵n个节点带边权的树,求树的直径长和直径必经边的个数。


思路

首先我们可以2次dfs求出一条直径和直径长度,第一问解决。
显然直径必经边一定是一段连续路径。
我们再写一个dfs求直径上的点向直径外的子树深度。
从右往左遍历直径,
如果子树深度等于到右端点距离,则从左端点到子树末端还有一条直径,剪掉右端;
如果等于到左端点距离,剪一次即可。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define N 200020
int fa[N],head[N],tot = 0,next[N << 1],to[N << 1],val[N << 1];
int n,p;
long long dmt,dep[N];
bool ond[N],flag;
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (num << 3) + (num << 1) + ch - '0';return sgn ? num : -num;
}
inline void addedge(int u,int v,int w){next[++tot] = head[u];to[tot] = v;val[tot] = w;head[u] = tot;}
void dfs1(int u,int f)
{
fa[u] = f;
for(register int i = head[u],v = to[i];~i;v = to[i = next[i]])
{
if(v == f) continue;
dep[v] = dep[u] + val[i];
if(dep[v] > dmt) p = v,dmt = dep[v];
dfs1(v,u);
}
}
void dfs2(int u,int f)
{
for(register int i = head[u],v = to[i];~i;v = to[i = next[i]])
{
if(v == f || ond[v]) continue;
dep[v] = dep[u] + val[i];
if(dep[v] > dmt) dmt = dep[v];
dfs2(v,u);
}
}
int main()
{
memset(head,-1,sizeof(head));
n = getint();
for(int i = 1,a,b,c;i < n;i++)
{
a = getint();b = getint();c = getint();
addedge(a,b,c);addedge(b,a,c);
}
dfs1(1,0);int l = p;dep[p] = dmt = 0;dfs1(l,0);int r = p; //find the diameter
printf("%lld\n",dmt);
for(int i = r;i;i = fa[i]) ond[i] = 1; //mark the points on the diameter
int ll = l,rr = r;
for(int i = fa[rr];i != ll;i = fa[i])
{
int ld = dep[i],rd = dep[rr] - dep[i];
dep[i] = dmt = 0;
dfs2(i,0);
if(dmt == rd) r = i;
if(dmt == ld &&!flag) flag = 1,l = i;
}
dmt = 1;for(int i = fa[r];i != l;i = fa[i]) dmt++;
printf("%d\n",dmt);
return 0;
}