自动搬运

查看原文

来自洛谷，原作者为

	disangan233 ディストピア

搬运于2025-08-24 21:57:53，当前版本为作者最后更新于2019-08-13 19:10:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

瞎扯

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

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

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

题意简述

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

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

做法

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

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

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

• 如果 $f(v)+1\leq size(u)-size(v)-1$，那么以 $v$ 为根的子树将会被全部消完，$f(u) = size(u) \bmod 2$
• 否则，我们应该尽可能消去 $f(v)+1$，那么 $f(u)=f(v)+1-(size(u)-size(v)-1)$。

考虑求所有点的可行性，在移到 $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;
}