题解 P3304 【[SDOI2013]直径】

· · 题解

首先求出直径这个简单，只要dfs一遍就行了。

我们再考虑第二问。要求的是所有直径都经过的边数。

所以我们先任意求出一条直径，记录这条直径上的点。

再对每个直径上的点都dfs，求出以这个点为起点的最长链（当然不能包括直径上的其它点），长度用dis[i]表示。

ls[i]表示这个点到直径左端点的距离。

rs[i]表示这个点到直径右端点的距离。（左右随意定）

从左端点开始向右遍历直径，若到了j号点发现，dis[j]=rs[j]就可以跳出循环，因为j的右边的所有边都不可能是必经边。

因为我们找到了一条不经过它们的直径。

那么是不是左端点到j就是必经边了呢？显然不是的。

因为还有可能出现这种情况，即dis[k]=ls[k],这样就变成了k的左边的所有边都不可能是必经边。

所以我们还要类似的从刚才跳出循环的点开始向左寻找这个k点。

那么j到k的所有边就是必经边了。

#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;
}