专栏文章

solution - P12017

llittlebug
P12017题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3gb69
此快照首次捕获于
2025/12/01 19:56
3 个月前
此快照最后确认于
2025/12/01 19:56
3 个月前
查看原文
你说得对，但是我的确注意力不够惊人。/ll
dp 显然，但是直接 dp 是不好做的，情况太多了，所以看看能不能找点限制，发现是可以的。
注意到如果连了一条边 u→vu \to v，那么 vv 可达的点 uu 一定可达，且 vv 不可到达 uu，故必须满足 lu>lvl_u > l_v；同理若连边 u↔vu \leftrightarrow v，那么必须满足 lu=lvl_u = l_v。
有了这个性质之后，dp 需要考虑的情况就大大减少了。注意到 n≤5000n \le 5000，所以应该是一个 O(n2)O(n^2) 的 dp，考虑令 fu,if_{u,i} 为「子树 uu，uu 可达的点数为 ii」这个状态是否可达，转移考虑树上背包，直接分讨：
  • 若 lu=lvl_u = l_v，则此时有两种选择，连双向边或者不连边。
    • 若连双向边，那么 u,vu,v 的可达点集（下面简称点集）一定是相同的，所以直接把两边的点集并起来即可：
      fu,i+j←fu,iand⁡fv,jf_{u,i+j} \gets f_{u,i} \operatorname{and} f_{v,j}
    • 若不连边，则必须保证 fv,lv=1f_{v,l_v} = 1。同时可以原封不动地转移：
      fu,i←fu,if_{u,i} \gets f_{u,i}
  • 若 lu>lvl_u > l_v，则只能连 u→vu \to v 或不连边。
    • 若连 u→vu \to v，那么就相当于把 uu 的点集并上 vv 的点集，但是不影响 vv 的点集，于是就只能从 fv,lvf_{v,l_v} 转移：
      fu,i+lv←fu,iand⁡fv,lvf_{u,i+l_v} \gets f_{u,i} \operatorname{and} f_{v,l_v}
    • 若不连边，和 lu=lvl_u = l_v 不连边的情况是一样的，在满足 fv,lv=1f_{v,l_v} = 1 的前提下：
      fu,i←fu,if_{u,i} \gets f_{u,i}
  • 若 lu<lvl_u < l_v，则只能连 v→uv \to u 或不连边。
    • 若连 v→uv \to u，那么不会对 uu 的点集产生任何影响，不过 uu 关于其它点的选择会影响 vv 的点集。而我们最后的目的需要让 uu 合法，所以可以构造一种情况使得若 uu 合法则 vv 一定合法，也就是说 fv,lv−luf_{v,l_v-l_u} 需要为 11。然后因为不会对 uu 的点集产生影响所以转移还是原封不动：
      fu,i←fu,if_{u,i} \gets f_{u,i}
      同时这个构造也是充要的，因为如果没有方案能使得 uu 合法，那么也没有必要考虑 vv 是否合法了。
    • 若不连边，依然一样，在满足 fv,lv=1f_{v,l_v} = 1 的前提下：
      fu,i←fu,if_{u,i} \gets f_{u,i}
直接转移即可，注意枚举范围为 szusz_u 或 szvsz_v，就可以做到 O(n2)O(n^2) 的总时间复杂度。
同时过程中需要注意，如果可以判断出不存在一种转移方案使得 vv 合法，直接判为无解即可。
代码：
CPP
// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,a[N],sz[N];
vector <int> p[N];
bitset <N> f[N],g;

il bool dfs(int u,int ufa)
{
	sz[u]=1,f[u][1]=1;
	for(auto v:p[u]) if(v^ufa)
	{
		if(!dfs(v,u)) return 0;
		g=0;
		
		if(a[u]==a[v])
		{
			rep(i,0,sz[u]) rep(j,0,sz[v]) g[i+j]=g[i+j]|(f[u][i]&f[v][j]);
			if(f[v][a[v]]) rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
		}
		
		else if(a[u]>a[v])
		{
			if(!f[v][a[v]]) return 0;
			rep(i,0,sz[u]) g[i+a[v]]=g[i+a[v]]|f[u][i];
			if(f[v][a[v]]) rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
		}
		
		else
		{
			if(!f[v][a[v]]&&!f[v][a[v]-a[u]]) return 0;
			rep(i,0,sz[u]) g[i]=g[i]|f[u][i];
		}
		
		sz[u]+=sz[v],f[u]=g;
	}
	return 1;
}

il void solve()
{
	read(n),_::r(a,n),_::r(p,n-1,false);
	
	if(!dfs(1,0)) write((string)"NO");
	else write((string)(f[1][a[1]]?"YES":"NO"));
}
华风夏韵，洛水天依！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...