zcmimi's blog
查看原题

点击跳转

首先两次dfs找出任意一条直径

设直径为序列A,L_i为点i到直径左端的距离,R_i为点ii到直径右端的距离

可以发现这条直径把树分割成了若干棵子树,直径上每个点对应一颗子树

mxd_ii点对应子树的最大深度

从左到右枚举,直到mxd_i<L_i,得到l

从右到左枚举,直到mxd_i<R_i,得到r

序列Alr之间的点都是必须经过的点

#include<bits/stdc++.h>
typedef long long ll;
const int N=200011;
int n,cnt,head[N],f[N],mx;
ll d[N];
bool v[N];
struct edge{int to,nxt,w;}e[N<<1];
void add(int x,int y,int w){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
void dfs(int x){
    if(d[x]>d[mx])mx=x;
    fl(i,x)if(to!=f[x])
        f[to]=x,d[to]=d[x]+e[i].w,dfs(to);
}
ll mxd;
void DFS(int x){
    v[x]=1;
    if(d[x]>mxd)mxd=d[x];
    fl(i,x)if(!v[to]){
        d[to]=d[x]+e[i].w;
        DFS(to);
    }
}
ll L[N],R[N];
int main(){
    scanf("%d",&n);
    int x,y,w,t=0;
    for(int i=1;i<n;++i)
        scanf("%d%d%d",&x,&y,&w),
        add(x,y,w),add(y,x,w);
    dfs(1),f[mx]=d[mx]=0,dfs(mx);
    printf("%lld\n",d[mx]);

    int l=0,r=0,i;
    for(x=mx;x;x=f[x],++r){
        L[f[x]]=L[x]+d[x]-d[f[x]];
        R[x]=d[x];
        v[x]=1;
    }
    for(x=mx,i=0;++i,x;x=f[x]){
        mxd=0,d[x]=0,DFS(x);
        // printf("%d %d %d %lld\n",x,L[x],R[x],mxd);
        if(mxd==L[x])l=i;
        else if(mxd==R[x]){r=i;break;}
    }
    printf("%d\n",r-l);
}
LG 3304 [SDOI2013]直径
comment评论
Search
search