题解 CF1187E 【Tree Painting】

· · 题解

前言

您完全可以略过这段。

校内模拟赛的时候一位大奆佬搬了这题。

然后我切了。

个人认为这题是一道不错的换根dp，虽然略显套路。

题意简述

给定一棵有 n 个结点的无根树，所有结点都是白色的。

第一次操作可以随意使一个结点染成黑色，之后每次操作可以使一个与黑色结点相邻的白色结点变成黑色。

每次操作可以获得的权值为被染成黑色的白色结点所在的白色连通块的结点数量。

求可以获得的最大权值。

感觉自己写的好绕。

题目分析与解答

不难发现只要选定了第一个被染色的结点，答案也就确定了。

所以有一个朴素做法就是以枚举每个结点为根，都做一次树形dp。

以某一结点为根，记 f_i 表示以 i 为根的子树中，首先把 i 染成黑色的答案。

方程就是 f_u = siz_u+\sum\limits_{v \in son_u} f_v。

其中 siz_u 表示以 u 为根的子树大小，也就是染色时的白色连通块大小。

这部分比较好理解就不画图举例啦。

时间复杂度 O(n^2) ，稳稳地暴毙。

然后就会自然而然地想到换根dp。

先考虑以任意一点为根，不妨记为 rt ，求出 f 数组。

然后记 g_i 表示以 i 结点为根时的答案。

显然有 g_{rt} = f_{rt}。

然后考虑 g 数组从父亲到儿子的转移。

以样例为例：

我们假设当前以 1 号为根，求出了 f 数组，也就是知道了 g_1 ，然后要求出 g_2 。

考虑一下答案的组成。

首先考虑 2 号结点的孩子的贡献，也就是图中蓝圈内的部分。这部分显然不会改变，贡献就是 f_2-siz_2 。

然后考虑父亲方向，也就是图中红圈部分对 g_2 的贡献。

那么除了以 2 号结点，与 1 一号结点相邻的其他子树都会对答案产生贡献，也就是说，我们只需要用以 1 号结点为根时的权值减去以 2 为根的子树的贡献即可，也就是 g_1-f_2-siz_2 。

不要忘了加上 n ，也就是初始的白色连通块大小。

综合一下上述两种方向的贡献，可以得到：g_2=(f_2-siz_2)+(g_1-f_2-siz_2)+n = g_1 + n - siz_2 \times 2 。

推广到所有结点，就可以得到：

g_u = g_{father_u} + n - siz_u \times 2

然后跑两遍 dfs 就愉快的解决啦。

Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>

using namespace std;

typedef long long ll;
const int MAXN = 200010;

int n;
struct edge{
    int ne, to;
    edge(int N=0, int T=0):ne(N),to(T){}
}e[MAXN<<1];
int fir[MAXN], num = 0;
inline void join(int a, int b)
{
    e[++num] = edge(fir[a], b);
    fir[a] = num;
}

ll siz[MAXN], f[MAXN], g[MAXN], ans = 0;

void dfs1(int u, int fa)
{
    siz[u] = 1;
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        f[u] += f[v];
    }
    f[u] += siz[u];
}
void dfs2(int u, int fa)
{
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == fa) continue;
        g[v] = n - siz[v] + g[u] - siz[v];
        dfs2(v, u);
    }
}

int main()
{
//  freopen("stars3.in","r",stdin);
//  freopen("stars.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        join(a, b);
        join(b, a);
    }
    dfs1(1, 0); 
    g[1] = f[1];
    dfs2(1, 0);
    ll ans = 0;
    for(int i=1;i<=n;i++)
        ans = max(ans, g[i]);
    printf("%lld\n",ans);
    return 0;
}

似乎只有我时而大括号换行，时而不换行？！