自动搬运

查看原文

来自洛谷，原作者为

	Mr_Az 我的尸体不会腐烂在泥土里，我会像鸟儿一样死在天空中。

搬运于2025-08-24 23:12:09，当前版本为作者最后更新于2025-04-29 16:46:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P12017 [NOISG 2025 Finals] Reachability

Algorithm:

树形背包。

Solution:

被薄纱了。

看到这道题让我会想到了省选的岁月，但其实两道题目并没有任何相似之处。

观察到 $u \rightarrow v$ 的边相当于让 $u$ 能够到达的点加上 $v$ 能够到的点的数量。这能够让我们发现两点之间可能的边的限制。具体而言如下所示：

1. 当 $l_u=l_v$ 时，$u,v$ 之间的边要么为双向边或者没有连边，原因是若为单向边则两个点能够到达点的数量至少差 $1$。
2. 当 $l_u \neq l_v$ 是，$u,v$ 之间的便要么为单向边（$l$ 值大的点连向 $l$ 值小的点）或者没有连边。

加上之前的观察，不难发现是一个树上背包的形式。所以考虑设 $f_{u,i}$ 代表在计算到 $u$ 的时候，$u$ 能够到达的点数量为 $i$ 是否合法。转移只要按照上面的分类讨论一下即可，具体而言如下所示：（$siz_i$ 为 $i$ 这个点的子树大小）

1. 当 $l_u=l_v$ 时：
   1. $u \leftrightarrow v$： $f_{u,i+j}|=f_{u,i}\&f_{v,j}(i \in [0,siz_u],j \in [0,siz_v])$。
   2. $u \not \rightarrow v$：此时必须满足 $f_{v,l_v}=1$。
2. 当 $l_u > l_v$ 时：
   1. $u \rightarrow v$： $f_{u,i+l_v}|=f_{u,i}(i \in [0,siz_u])$。
   2. $u \not \rightarrow v$：此时必须满足 $f_{v,l_v}=1$。
3. 当 $l_u<l_v$ 时：
   1. $u \leftarrow v$：此时必须满足 $f_{v,l_v-l_u}=1$。
   2. $u \not \rightarrow v$：此时必须满足 $f_{v,l_v}=1$。

不满足的情况可以直接输出 NO 退出。最后检查根节点是否合法即可。在实际实现的过程中会遇到 $f_{u,i}$ 在一个儿子被更新后去更新其他状态，所以需要辅助数组 $g_i$ 用来暂时存储 $f_{u,i}$ 的状态，更新完后重新赋值。

Code:

namespace Mr_Az{
	const int N=5008;
	int T=1;
	int n;
	int l[N],siz[N];
	bool f[N][2*N],g[2*N];
	vector<int> e[N];
	void dfs(int u,int fa){
		siz[u]=1;
		for(auto v:e[u]){
			if(v==fa) continue;
			dfs(v,u);
			if(l[u]==l[v]){// 所达城市数量一致
				// 1. 连边
				for(rint i=0;i<=siz[u];i++)
					for(rint j=0;j<=siz[v];j++)
						g[i+j]|=(f[u][i]&f[v][j]);
						
				// 2. 断开(下面必须要满足要求)
				if(f[v][l[v]]){
					for(rint i=0;i<=siz[u];i++) g[i]|=f[u][i];
				}
			}
			else{// 所达城市数量不一致
				if(l[u]>l[v]){// 1. u->v 或不连边
					if(!f[v][l[v]]){puts("NO");exit(0);}
					else{
						for(rint i=0;i<=siz[u];i++){
							g[i+l[v]]|=f[u][i];
							g[i]|=f[u][i];
						}
					}
				}
				else{// 2. v->u 或不连边
					if(!f[v][l[v]]&&!f[v][l[v]-l[u]]){puts("NO");exit(0);}
					for(rint i=0;i<=siz[u];i++) g[i]|=f[u][i];
				}				
			}
			siz[u]+=siz[v];
			for(rint i=0;i<=siz[u];i++) f[u][i]=g[i];
			mem(g,0);
		}
	}
	inline void solve(){
		read(n);
		for(rint i=1;i<=n;i++) read(l[i]);
		for(rint i=1,u,v;i<n;i++){
			read(u,v);
			e[u].pb(v);e[v].pb(u);
		}
		for(rint i=1;i<=n;i++) f[i][1]=1;
		dfs(1,0);
		if(f[1][l[1]]) puts("YES");
		else puts("NO");
	}
	inline void mian(){if(!T) read(T);while(T--) solve();}
}