题解 P3478 【[POI2008]STA-Station】

· · 题解

这是道蛮简单的树型dp呀，为什么会是蓝题啊orz 但是我这个wa了四次的人为什么有脸说这个

题目给的是无根树，那我们可以随便选择一个点（比如1号）作为根

这样 我们可以得到 以1为根的子结点个数son_size[1] 以1为根的子结点的深度和dep_sum[1]

接下来，我们考虑如何从1号点转移其他点

考虑i的儿子j,如果我们以j为根，那么j的所有子结点（显然包括j）的深度应该+1，i号点的其他子结点（显然包括i）的深度应该-1

所以，我们可以得出转移：

j是i的儿子，那么： f[j]=f[i]+n-2*son_size[i]

好，那么这道题的大致思路就ok了，细节上的话，就是数组记得开long long，最好写一个快读，不然有几率t掉第九个点，然后dfs和dp的过程中，最好通过传入父结点作为参数的方式搜索 如果用vis数组，有可能会忘掉memset这个操作，这样就GG了

下面是代码quq

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
inline int read()
{
  int ans=0,op=0;
  char ch=getchar();
  while(ch<'0'||ch>'9')
    {
      if(ch=='-') op=-1;
      ch=getchar();
    }
  while(ch>='0'&&ch<='9')
    {
      ans*=10;
      ans+=ch-'0';
      ch=getchar();
    }
  return ans*op;
}
int n;
ll dep[maxn];
ll dep_sum[maxn];
ll son_size[maxn];
ll f[maxn];
struct edge
{
    int to,next;
}e[maxn*2];
int fir[maxn],alloc;
void adde(int u,int v)
{
    e[++alloc].next=fir[u];
    fir[u]=alloc;
    e[alloc].to=v;
}
void dfs1(int u,int fa)
{
    son_size[u]=1;
    for(int i=fir[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        vis[v]=1;
        dep[v]=dep[u]+1;
        dfs1(v,u);
        son_size[u]+=son_size[v];
    }
    return;
}
void dfs2(int u,int fa)
{
    for(int i=fir[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        vis[v]=1;
        dfs2(v,u);
        dep_sum[u]+=dep_sum[v];
    }
}
void dp(int u,int fa)
{
    for(int i=fir[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        vis[v]=1;
        f[v]=max(f[v],f[u]+n-2*son_size[v]);
        dp(v,u);
    }
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        adde(u,v);
        adde(v,u);
    }
    dep[1]=1;
    dfs1(1,0);
    for(int i=1;i<=n;i++) dep_sum[i]=dep[i];
    dfs2(1,0);
    f[1]=dep_sum[1];
    dp(1,0);
    ll ans=0;
    ll maxm=0;
     for(int i=1;i<=n;i++) 
        if(f[i]>maxm)
            ans=i,maxm=f[i];
    printf("%lld",ans);
}