[SDOI2013]直径

题目大意：
　　给你一棵n个结点的带边权的树，求该树直径必经边的个数。

思路：
　　显然直径必经的所有边的肯定是一个直径上的连续一段。
　　（若超过一段，则出现环，就不是树了）
　　首先求出原树的任一直径。
　　预处理出该直径上从结点i出发，不经过直径上其它结点的最长链长度far[i]。
　　从直径的两端往里缩，如果当前缩到的点i的far[i]等于i到被缩的那一端的距离，就说明直径的这一段至少有两种不重合的情况，肯定不是必经部分。
　　最后看一下中间没有被缩的部分经过了几个边。

#include<cstdio>
#include<cctype>
#include<vector>
typedef long long int64;
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=200001;
struct Edge {
    int to,w;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &w) {
    e[u].push_back((Edge){v,w});
    e[v].push_back((Edge){u,w});
}
bool mark[N];
int from[N],to[N],u,v;
int64 dis[N],far[N];
void dfs(const int &x) {
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i].to,&w=e[x][i].w;
        if(y==from[x]) continue;
        from[y]=x;
        dis[y]=dis[x]+w;
        dfs(y);
    }
}
void dp(const int &x,const int &par) {
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i].to,&w=e[x][i].w;
        if(y==par||mark[y]) continue;
        dp(y,x);
        far[x]=std::max(far[x],far[y]+w);
    }
}
int main() {
    const int n=getint();
    for(register int i=1;i<n;i++) {
        const int u=getint(),v=getint(),w=getint();
        add_edge(u,v,w);
    }
    dfs(1);
    for(register int i=1;i<=n;i++) {
        if(dis[i]>dis[u]) u=i;
    }
    dis[u]=from[u]=0;
    dfs(u);
    for(register int i=1;i<=n;i++) {
        if(dis[i]>dis[v]) v=i;
    }
    for(register int x=v;x;x=from[x]) {
        mark[x]=true;
        to[from[x]]=x;
    }
    for(register int x=v;x;x=from[x]) {
        dp(x,0);
    }
    int l=u,r=v;
    for(register int x=v;x;x=from[x]) {
        if(far[x]==dis[v]-dis[x]) r=x;
    }
    for(register int x=u;x;x=to[x]) {
        if(far[x]==dis[x]) l=x;
    }
    int len=0;
    for(register int x=r,i=0;x;x=from[x],i++) {
        if(x==l) len=i;
    }
    printf("%lld
%d
",dis[v],len);
    return 0;
}