【解题报告】[清华集训2017]榕树之心

题目链接

---

前言

其实这题算是六月zzy讲课时，一道atcoder上面的题的加强版，当时因为某些不可抗力打了一半，今天回头来把这道题切了

题意

给你一棵树，一开始在 $1$ 号结点(根)有一个棋子，你需要将棋子向每个除了根节点以外的点都移动一格(必须先拓展其父结点)，输出棋子是否有可能最终位于 $i$ 号结点。多组数据

题解

我们先从部分分开始考虑

subtask1[ 10pts ]

直接裸的暴力，没什么好说的

subtask2[ 10pts ]

emm……太菜了，没想出来有什么特殊的做法

subtask3[ 10pts ]

我们设一个 $f_i$ 为从以 $i$ 为根的子树开始移动，最终能离 $i$ 最近的距离
很显然的，我们可以通过树形DP来转移
我们先处理出每个结点的重儿子记为 $v$

如果 $f_v+1\le size_i-size_v-1$ ，从重儿子中移动，离重儿子最近的距离+1，即为离当前结点的距离，如果此距离小于其它可以移动的结点数量，则当 $size_i-1\mod 2=0$ 时，则 $f_i=0$ ，否则即 $f_i=1$
反之，则 $f_i=f_v+1-(size_i-size_v-1)$

很显然的，这个做法只考虑了以 $i$ 为根的子树，没有考虑其余不属于其子树的结点，所以我们只能处理 $1$ 号结点

subtask4[ 35pts ]

我们考虑 subtask3 的做法，是只能处理当前结点的子树，我们考虑对于任意点 $i$ ，先将棋子移到 $i$ 结点，并将 $1\to i$ 缩成新根，然后重复 subtask3 即可，复杂度 $O(n^2)$

subtask5[ 35pts ]

考虑对上述做法优化。我们可以发现，当我们处理新根是，我们只需要除开缩成的点后的重儿子，很显然的，我们可以直接从 $1$ 号结点开始遍历，同时维护一个 $1\to u$ 缩点后的重儿子mson

即$ mson=\max(mson(u),mson)$
特别的，当 $mson=u$ 时，我们用次重儿子进行判断即可，所以我们还要维护一个次重儿子

每个点的重儿子和次重儿子可以和 $f_i$ 一样先预处理好，当我们遍历向下一个结点拓展时讨论情况更新即可

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<math.h>
#define maxn 200005
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int T,W,n,ans[maxn],fa[maxn];
int si[maxn],f[maxn],dep[maxn];
int mson[maxn],cmson[maxn];
int head[maxn],cnt_edge;
struct eage
{
    int v,last;
}e[maxn<<2];

inline int read(void)
{
    int num,sign=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')sign=0;
    num=c-'0';
    while(isdigit(c=getchar()))num=(num<<3)+(num<<1)+c-'0';
    return sign?num:-num;
}

inline void clear(void)
{
    memset(head,0,sizeof head),cnt_edge=0;
    memset(mson,0,sizeof mson);
    memset(cmson,0,sizeof cmson);
    memset(f,0,sizeof f);
}


inline void addeage(int u,int v)
{
    e[++cnt_edge].last=head[u],e[cnt_edge].v=v,head[u]=cnt_edge;
    e[++cnt_edge].last=head[v],e[cnt_edge].v=u,head[v]=cnt_edge;
}

void dfs1(int u,int la)
{
    si[u]=1,dep[u]=dep[la]+1,fa[u]=la;
    int maxson=0,cmaxson=0;
    for(register int i=head[u];i;i=e[i].last)
    {
        int v=e[i].v;
        if(v==la)continue;
        dfs1(v,u);
        si[u]+=si[v];
        if(si[v]>maxson)cmaxson=maxson,maxson=si[v],cmson[u]=mson[u],mson[u]=v;
        else if(si[v]>cmaxson)cmaxson=si[v],cmson[u]=v;
    }
    if(mson[u])
    {
        if(f[mson[u]]+1<=si[u]-maxson-1)f[u]=(si[u]-1)%2;
        else f[u]=f[mson[u]]-si[u]+maxson+2;
    }
}
inline int getmax(int x,int y){return si[x]>=si[y]?x:y;}
inline int getmin(int x,int y){return si[x]<si[y]?x:y;}

void dfs2(int u,int la,int maxid,int cmaxid)
{
    if(u!=1)
    {
        int sum=n-dep[u];
        if(f[maxid]+1<=sum-si[maxid])ans[u]=!(sum%2);
        else ans[u]=!(f[maxid]+1-sum+si[maxid]);
    }
    for(register int i=head[u];i;i=e[i].last)
    {
        int v=e[i].v;
        if(v==la)continue;
        if(v==maxid)dfs2(v,u,getmax(cmaxid,mson[v]),getmax(cmson[v],getmin(cmaxid,mson[v])));
        else if(v==cmaxid)dfs2(v,u,getmax(maxid,mson[v]),getmax(cmson[v],getmin(maxid,mson[v])));
        else dfs2(v,u,getmax(maxid,mson[v]),getmax(cmaxid,getmax(cmson[v],getmin(maxid,mson[v]))));
    }
}

signed main(void)
{
    W=read(),T=read();
    while(T--)
    {
        clear();
        n=read();
        for(register int i=1;i<n;++i)addeage(read(),read());
        dfs1(1,0),ans[1]=!f[1];
        dfs2(1,0,mson[1],cmson[1]);
        if(W==3)
            printf("%d\n",ans[1]);
        else
        {
            for(register int i=1;i<=n;++i)printf("%d",ans[i]);
            printf("\n");
        }
    }
    return 0;
}