【洛谷】题解 P4228 【榕树之心】

Luogu
LOJ
UOJ
这题面写得也太好了吧 QAQ

分析

我们先考虑怎么算根节点的答案。
先假设它只有两棵子树 $u$ 和 $v$，榕树之心在根节点处。
如果 $u$ 长出一个节点，$v$ 长出一个节点，那么榕树之心还在根节点处，相当于这两次操作抵消掉了。
那么我们只需要判断根节点的所有子树能否相互抵消掉。
注意每棵子树是可以自行抵消一部分的，因此可以设 $f_u$ 表示 $u$ 子树内最多可以自行抵消多少对。
考虑 $f_u$ 如何转移。设最大的子树的根为 $h$，则

• 如果 $sz_h-2\times f_h\leq sz_u-1-sz_h$，则最大的子树可以被消掉，剩下的子树中还可以再消掉偶数个点，因此此时 $f_u=\left\lfloor\frac{sz_u-1}{2}\right\rfloor$。
• 否则，其它所有的子树都不可以把最大的子树消掉，因此此时 $f_u=f_h+sz_u-1-sz_h$。

这样子就只需要做一遍树形 DP 就能得到 $f$ 了。
考虑如何算根节点的答案。我们还是找到根节点的最大的子树，设它的根为 $h$，那么只需要判断 $sz_h-2\times f_h$ 是否小于等于 $n-1-sz_h$ 就好了。
然后我们再扩展到算任意点的答案。我们可以认为是先把榕树之心从根移到了当前节点，因此只需要把根到当前节点的链缩成一个点视为根即可。这样子需要维护缩点的最大子树，因此需要预处理出每个节点的次大子树。

代码

                    
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,ans[N];

struct edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;
inline void addEdge(int u,int v) {
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],sz[N],hson[N],hson2[N],f[N];
inline void dfs1(int u,int fa) {
    dep[u]=dep[fa]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson2[u]=hson[u],hson[u]=v;
        else if (sz[v]>sz[hson2[u]]) hson2[u]=v;
    }
    if (sz[hson[u]]-2*f[hson[u]]<=sz[u]-1-sz[hson[u]]) f[u]=(sz[u]-1)/2;
    else f[u]=f[hson[u]]+sz[u]-1-sz[hson[u]];
}
inline int cmp(int x,int y) { return sz[x]>sz[y]?x:y; }
inline void dfs2(int u,int fa,int h) {
    int tmp=cmp(hson[u],h);
    if (sz[tmp]-2*f[tmp]<=n-dep[u]-sz[tmp]) ans[u]=(n&1)==(dep[u]&1);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs2(v,u,v==hson[u]?cmp(hson2[u],h):cmp(hson[u],h));
    }
}

inline void init() {
    cnt=0,memset(head,0,sizeof(head));
    memset(hson,0,sizeof(hson));
    memset(hson2,0,sizeof(hson2));
    memset(ans,0,sizeof(ans));
}

int main() {
    int W=read(),T=read();
    while (T--) { init();
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read();
            addEdge(u,v),addEdge(v,u);
        }
        dfs1(1,0); dfs2(1,0,0);
        if (W==3) putchar(ans[1]+'0');
        else for (re int i=1;i<=n;++i) putchar(ans[i]+'0');
        puts("");
    }
    return 0;
}