LOJ#2330 榕树之心树形dp

瞎扯

这个题和\(\mathsf{ISIJ2019 Au}\)神仙学弟\(\mathsf{\color{red}c}\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

namespace fast_io

{

    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=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;

	    x=nc-48;while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48);return x*y;

	}

    in db gf() {re a=read(),b=(nc!='.')?0:read(),c=ceil(log10(b));return (b?a+(db)b/pow(10,c):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;

}

巴特西

LOJ#2330 榕树之心树形dp

瞎扯

题意简述

做法

Code

最新文章

热门文章

巴特西

LOJ#2330 榕树之心 树形dp

瞎扯

题意简述

做法

Code

最新文章

热门文章

LOJ#2330 榕树之心树形dp