题解 P3478 【[POI2008]STA-Station】

· · 题解

吐槽

我听英文题面说，有多组解的时候，任意输出一个即可。

结果数据是要求输出编号最小的那个。

很显然的一个树形动规。

设size_k代表k的孩子的个数。

设f_k代表k的结果。

考虑先令1为根结点，暴力求出f_1，在此过程中可以顺带求出整个size数组。

以样例为例

如图，红圈内的结点个数为size_4，在样例中size_4=7，绿圈中的结点个数为size_1，在样例中size_1=1，size数组的定义以此类推。

当我们假设1号结点所联通的点为根时，在样例中，只能为4号结点，此时，我们已经求出f_1=18和整个size数组。

为了文章可读性起见，在这里列出有作用的：size_1=1，size_4=7

那么我们的问题就是，如何使用已知的f_1和size数组，求出f_4。

我们发现，当根转移到4号结点的时候，size_4所包含的全部结点的深度都减1了，因此根转移到4号结点首先要付出size_4的代价。

其次，我们发现，不被size_4所包含的其他所有结点的深度都加1了，因此根转移到4号结点可以获得n-size_4的收益。

整理一下：f_4=f_1+n-2×size_4

所以在样例中，f_4=12，读者可以自行画图检验。

推广到所有的情况下，当当前根节点为x，将向k号结点转移时，就可以计算出f_k=f_x+n-2×size_k

求出整个f数组的过程需要由递归完成。

注意

需要开long long

在求f_1的过程中只能传两个参数，所以dep需要用数组记录。

代码：

#include<iostream>
#include<cstdio>

using namespace std;
#define maxn 2000007
#define maxn1 1000007
long long int x,y,tot,n,Head[maxn],Next[maxn],u[maxn],v[maxn];
long long int size[maxn1],f[maxn1],ans,kkk,dep[maxn1];
bool vis[maxn1],gfg[maxn1];
inline int max(int a,int b)
{
    return a>b?a:b;
}
inline void read(long long &x)
{
    int fh;
    char ch;
    x=0;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;
        ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
}
inline void add()
{
    u[++tot]=x,v[tot]=y;
    Next[tot]=Head[x],Head[x]=tot;
    u[++tot]=y,v[tot]=x;
    Next[tot]=Head[y],Head[y]=tot;//建边
}
long long int dfs(int x,int root)//求f1和size
{
    int sum=0;
    vis[x]=1;
    size[x]=1;
    for(int i=Head[x];i;i=Next[i])
    {
        if(vis[v[i]]) continue;
        dep[v[i]]=dep[x]+1;
        sum+=dfs(v[i],x);
    }
    size[root]=size[root]+size[x];
    return sum+dep[x];
}
void zy(int x,int root)//转移
{
    gfg[x]=1;
    for(int i=Head[x];i;i=Next[i])
    {
        if(gfg[v[i]]) continue;
        f[v[i]]=f[x]+n-2*size[v[i]];
        if(f[v[i]]>ans)
        {
            ans=f[v[i]];
            kkk=v[i];
        }
        if(f[v[i]]==ans) kkk=min(kkk,v[i]); 
        zy(v[i],x);
    }
}
int main()
{
    read(n);
    for(register int i=1;i<n;i++)
    {
        read(x);
        read(y);
        add();
    }
    f[1]=dfs(1,0);
    gfg[1]=1;
    ans=f[1];
    kkk=1;
    zy(1,0);
    printf("%d\n",kkk);
}