题解 P3304 【[SDOI2013]直径】
破壁人
2018-01-04 19:49:51
首先求出直径这个简单，只要dfs一遍就行了。
我们再考虑第二问。要求的是所有直径都经过的边数。
所以我们先任意求出一条直径，记录这条直径上的点。
再对每个直径上的点都dfs，求出以这个点为起点的最长链（当然不能包括直径上的其它点），长度用dis[i]表示。
ls[i]表示这个点到直径左端点的距离。
rs[i]表示这个点到直径右端点的距离。（左右随意定）
从左端点开始向右遍历直径，若到了j号点发现，dis[j]=rs[j]就可以跳出循环，因为j的右边的所有边都不可能是必经边。
因为我们找到了一条不经过它们的直径。
那么是不是左端点到j就是必经边了呢？显然不是的。
因为还有可能出现这种情况，即dis[k]=ls[k],这样就变成了k的左边的所有边都不可能是必经边。
所以我们还要类似的从刚才跳出循环的点开始向左寻找这个k点。
那么j到k的所有边就是必经边了。
```cpp
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[200001],b[200001];
int last[200001],u,v,next[200001];
long long dis[200001],mmm[200001],op;
bool vv[200001];
void dfs1(int o,long long p,int q)
{
if(p>op){op=p;u=o;}
for(int i=0;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs1(a[o][i],p+b[o][i],o);
}
}
void dfs2(int o,long long p,int q)
{
last[o]=q;
dis[o]=p;
if(p>op){op=p;v=o;}
for(int i=0;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs2(a[o][i],p+b[o][i],o);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x].push_back(y);
b[x].push_back(z);
a[y].push_back(x);
b[y].push_back(z);
}
memset(vv,0,sizeof(vv));op=0;
dfs1(1,0,0);
memset(vv,0,sizeof(vv));op=0;
dfs2(u,0,0);
int distance=dis[v];
cout<<dis[v]<<endl;
memset(vv,0,sizeof(vv));
for(int i=v;i!=0;i=last[i]) vv[i]=true;
for(int i=v;i!=0;i=last[i])
{
op=0;
dfs1(i,0,0);
mmm[i]=op;
}
int j=v;
for(int i=last[v];i!=0;i=last[i]) next[i]=j,j=i;
int ans=0;
int i;
for(i=j;i!=0;i=next[i])
if(dis[v]-dis[i]==mmm[i]) break;
for(;i!=0;i=last[i])
{
if(dis[i]==mmm[i]) break;
ans++;
}
cout<<ans<<endl;
return 0;
}
```