本文共 1792 字，大约阅读时间需要 5 分钟。
题目链接：
思路：虚树，取两点间的lca，构造成一颗新的树；求（直径+1）/2即可
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define pi (4*atan(1.0))#define eps 1e-8#define bug(x) cout<<"bug"< < =0 ;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i];y=fa[y][i]; } } if(x==y) return x; else return fa[x][0];}int h[M],ans,far,pos;struct f{ int v,w,nex;}edge2[N<<1];int head2[N],edg2;void add2(int u,int v,int w){ edge2[++edg2]=(f){v,w,head2[u]}; head2[u]=edg2;}bool cmp(int u, int v) { return in[u] < in[v];}bool check(int u, int v) { return in[u] <= in[v] && in[v] <= out[u];}int build(int A[], int tot) { std::sort(A + 1, A + 1 + tot, cmp); for(int i = 2, old_tot = tot; i <= old_tot; i++) { A[++tot] = RMQ_LCA(A[i - 1], A[i]); } std::sort(A + 1, A + 1 + tot, cmp); tot = std::unique(A + 1, A + 1 + tot) - A - 1; std::stack S; S.push(A[1]); for(int i = 2; i <= tot; i++) { while(!S.empty() && !check(S.top(), A[i])) S.pop(); int u = S.top(), v = A[i]; add2(u,v,deep[v]-deep[u]); add2(v,u,deep[v]-deep[u]);//u, v, deep[v] - deep[u]); S.push(v); } return tot;}void dfs1(int u,int fa,int val){ if(val>far)far=val,pos=u; for(int i=head2[u];i!=-1;i=edge2[i].nex) { int v=edge2[i].v; int w=edge2[i].w; if(v==fa)continue; dfs1(v,u,val+w); }}void dfs2(int u,int fa,int val){ ans=max(ans,val); for(int i=head2[u];i!=-1;i=edge2[i].nex) { int v=edge2[i].v; int w=edge2[i].w; if(v==fa)continue; dfs2(v,u,w+val); }}int main(){ init(); memset(head2,-1,sizeof(head2)); int n; scanf("%d",&n); for(int i=1;i
；
转载于:https://www.cnblogs.com/jhz033/p/7676795.html