题解 P4228 【榕树之心】

· · 题解

瞎扯

这个题和 \mathsf{ISIJ2019 Au} 神仙学弟 \mathsf{c}\color{red} \mathsf {hangruinian2020} 争辩了半个多小时。

概括一下就是《浅谈全球 \mathsf{Top10} 神仙对于一类图论问题的感性证明的瞎扯》。

所以这篇题解里将会讲一些特别细的内容，而不是"显然"。

题意简述

给你一棵有根树和一个动点，动点一开始位于根结点 1。一开始这棵树只有根结点，每次可以在已有的结点上沿原树边向外扩展一个结点，并使动点沿着新结点的方向移动一个结点。

请求出每个结点在原树被完全扩展后，动点是否能停留在第 i 个结点。

做法

首先这个题一眼 30pts，考虑 \mathsf{Subtask 3} 的做法。

考虑每一个结点不同儿子子树的两次操作会相互抵消，显然移回当前节点的最优方案一定是剩下来自重儿子子树的结点，所以尽可能消除重儿子子树即可。

令 f(u) 为动点在以 u 为根的子树扩展结束后与 u 的距离，令 v=son(u)，我们想办法写出转移方程。

考虑求所有点的可行性，在移到 u 时我们已经处理了 1\to u 的路径和路径上结点的一些子树，显然存在一种策略可以可以使子树相互消除，那么问题就转化成和 \mathsf{Subtask 3} 类似的问题，把 1\to u 的路径压缩起来当做新根即可。

考虑暴力合并是 O\left(n^2 \right) 的，需要优化时间复杂度。

发现父亲节点对于当前重儿子的贡献只有子树大小之和以及 son(fa(u))，所以可以直接合并。但是 size(son(u))==size(son(fa(u))) 时是不能合并的，所以维护次重儿子并起来就好了。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in ll read()
    {
        ll x=0,y=1;while(nc=gc(),(nc<48||nc>57)&&nc!=-1)if(nc==45)y=-1;Bi=1;
        x=nc-48;while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*y;
    }
    in db gf() {re a=read(),b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi):a);}
    in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
    in void flush() {if(C>1<<22) ot();}
    template <typename T>
    in void write(T x,char t)
    {
        re y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
    }
    in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=1e6+5;
int type,t,n,f[N],ans[N],son[N],siz[N];
vector<int>g[N];
in void add(re x,re y) {g[x].push_back(y);g[y].push_back(x);}
void dfs1(re u,re fa)
{
    siz[u]=1;
    for(auto v:g[u]) if(v!=fa)
    {
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
    if(!son[u]) return;
    if(f[son[u]]+1<=siz[u]-siz[son[u]]-1) f[u]=(siz[u]-1)&1;
    else f[u]=f[son[u]]+1-(siz[u]-siz[son[u]]-1);
}
void dfs2(re u,re fa,re pre,re sum)
{
    re sson=0;
    if(u>1)
    {
        re sz=siz[u]+sum,pos=0;
        if(siz[son[u]]>siz[pre]) pos=son[u]; else pos=pre;
        if(f[pos]+1<=sz-siz[pos]-1) ans[u]=((sz-1)&1);
        else ans[u]=f[pos]+1-(sz-siz[pos]-1);
    }
    for(auto v:g[u]) if(v!=fa&&v!=son[u]&&siz[v]>siz[sson]) sson=v;
    for(auto v:g[u]) if(v!=fa)
    {
        re nw=(v==son[u]?sson:son[u]),tmp=siz[nw]>siz[pre]?nw:pre;
        dfs2(v,u,tmp,sum+siz[u]-siz[v]-1);
    }
}
int main()
{
    type=read();t=read();
    while(t--)
    {
        re n=read();
        for(re i=1;i<=n;i++) f[i]=son[i]=ans[i]=siz[i]=0,g[i].clear();
        for(re i=1;i<n;i++) add(read(),read());
        dfs1(1,0);ans[1]=f[1];dfs2(1,0,0,0);
        if(type==3) write(!ans[1],'\n');
        else 
        {
            for(re i=1;i<=n;i++) sr[++C]=(!ans[i])?'1':'0';
            sr[++C]='\n';
        }
    }
    return ot(),0;
}