CF1187E Tree Painting 换根法

思路

典型的树形\(DP\)

然而并不能一次\(dfs\)求出答案

要用换根法

按照个人理解的话

换根法就是

在选起点做树形\(DP\)时

对于\(ans[1]\)//以\(1\)为起点的答案值

我们可以 通过\(O(1)\) 算出\(ans[sonof1]\)

实现

对于这道题

我们先以\(1\)为根

容易写出

inline void dfs(int x,int fa)
{
    size[x] = 1;
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == fa) continue;
        dfs(v,x);
        size[x] += size[v];
    }
    ans[1] += size[x];
}

转移的话

先来张图

对于\(x\)

\(ans[y]=f[xson1]+f[xson2]+f[xson3]+size[x]+size[y]+f[yson1]+f[yson2]+f[yson3]\)

有\(size[x]=n-size[y]\)

\(ans[y]=ans[x]+n-size[y]-size[y]\)

\(code\)

开\(longlong\)

#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 2e5 + 10;
struct node
{
    int v,next;
}edge[MAXN << 1];
int cnt,size[MAXN],head[MAXN];
long long pr,ans[MAXN];
inline void addedge(int u,int v)
{
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
inline void dfs(int x,int fa)
{
    size[x] = 1;
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == fa) continue;
        dfs(v,x);
        size[x] += size[v];
    }
    ans[1] += size[x];
}
inline void dfs2(int x,int fa)
{
    for(reg i = head[x];i;i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == fa) continue;
        ans[v] = ans[x] + size[1] - 2 * size[v];
        pr = max(pr,ans[v]);
        dfs2(v,x);
    }
}
int main()
{
    int n = Read(1);
    for(reg i = 1;i < n;i++)
    {
        int u = Read(1),v = Read(1);
        addedge(u,v),addedge(v,u);
    }
    dfs(1,0);
    dfs2(1,0);
    printf("%lld",pr);
    return 0;
}

//f[x] = n + f[xson]

//f[y] = n + f[yson] = f[x] + n - 2 * size[y]