题解 P3478 【[POI2008]STA-Station】

· · 题解

如题，这是一题非常明显的树形dp，那么我们就开始根据树形dp的思想解决这个问题。题意是找到这棵树的一个点，使得这个点成为根时这棵树的总深度（即每个节点的深度之和）最大。那么首先我们很明显的知道，对于一棵树，任何的节点我们都可以把它看作根，那么我们完全可以假设第一个点为根，并以此求出每个节点的子树大小以及所处深度。这是非常简单的，类似于树链剖分的第一步dfs。

现在我们考虑，如果我们转换了这棵树的根，会发生什么情况：

如果我们吧根从x变成y，且St.x=fa[y]，即x是y的父亲节点（在第一次dfs的情况下），那么就非常显然了，b的子树节点全都-1，其余的都+1，这就是这一次操作对答案的影响。

但是我们大可以没有必要每次都对子树进行query，那么我们在第一次dfs的时候求出每个点的子树权值就好了，这是非常简单的、、、

代码如下：

#include<bits/stdc++.h>
#define N 1000100
using namespace std;
typedef long long ll;
struct Edge{
    int u,v,next;
}G[2\*N];
int d[N];
int tot=0,head[4\*N];ll size[N],n,dw[N],up[N],fa[N];
void addedge(int u,int v){
    G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
    G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot;
}
void dfs1(int u,int f){
    size[u]=1;
    for(int i=head[u];i;i=G[i].next){
        int v=G[i].v;if(v==f)continue;
        fa[v]=u;d[v]=d[u]+1;
        dfs1(v,u);
        size[u]+=size[v];
        dw[u]+=dw[v]+size[v];
    }
}
void dfs2(int u){
    if(u>1)up[u]=up[fa[u]]+dw[fa[u]]-dw[u]-2\*1LL\*size[u]+n;
    for(int i=head[u];i;i=G[i].next){
        int v=G[i].v;if(v==fa[u])continue;
        dfs2(v);
    }
}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x\*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f\*x;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addedge(u,v);
    }
    dfs1(1,0);dfs2(1);ll ans=0;
    //for(int i=1;i<=n;i++)printf("%d ",up[i]);
    int num;
    for(int i=1;i<=n;i++){
        if(up[i]+dw[i]>ans)ans=up[i]+dw[i],num=i;
    }
    printf("%d\n",num);
    return 0;
}