自动搬运

查看原文

来自洛谷，原作者为

	SunsetVoice **

搬运于2025-08-24 23:02:16，当前版本为作者最后更新于2024-08-22 16:11:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

好题啊（赞赏）

然后自信提交，获得了 $30$ 分的好成绩。

设 $dp_{i,0}$ 为 $i$ 方案中不包含 $i$，$i$ 的子树的方案总数；$dp_{i,1}$ 为包含 $i$ 的方案，$i$ 的子树的方案总数。

显然，如果要跨子树选择，必须选 $i$，因为 $\text{LCA}(u,v)$ 肯定有 $i$ 存在，再加上 $i$ 自身，一共是 $\prod dp_{v,0}+dp_{v,1}+1$.

若不选 $i$，则继承了任意一颗子树里的方案。总方案数为 $\sum dp_{v,0}+dp_{v,1}$。

转移都是 $O(n)$ 的。

然后自信提交，获得了 $30$ 分的好成绩。

这里有一个小优化，显然一次改变 $i$ 只影响 $i$ 到 $1$ 上的所有路径，删去即可，注意除法要有理数取模。

然后自信提交，获得了 $30$ 分的好成绩。

复杂度仍是 $O(nm)$，由于数据造的太好，没有骗到任何分。

我们考虑树上前缀积算子树贡献系数 $g_i$，显然这玩意可以预处理。

于是答案为 $dp_{1,0}+dp_{1,1}-(dp_{pos,0}+dp_{pos,1})\times g_{pos}$

复杂度为 $O(n\log mod)$

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int siz[500001] = {0},n,m,dp[500001][2] = {0},db = 0;
int fdp[500001][2] = {0};
vector<int>e[500001];
int vis[500001] = {0};
const int mod = 998244353;
int fa[500001] = {0};
int g[500001] = {0};
int qpow(int x,int y){
	int ret = 1; 
	while(y){
		if(y&1){
			ret*=x;
			ret%=mod;
		}
		x*=x;
		x%=mod;
		y>>=1;
	}
	return ret;
}
void dfs(int pos){
	vis[pos] = 1;
	int dyc = 1;
	for(int i = 0;i<e[pos].size();i++){
		if(!vis[e[pos][i]]){
			fa[e[pos][i]] = pos;
			//cout<<pos<<" "<<e[pos][i]<<endl;
			dfs(e[pos][i]);
			dp[pos][0]+=dp[e[pos][i]][0]+dp[e[pos][i]][1];
			dp[pos][0]%=mod;
			//cout<<dp[e[pos][i]][0]+dp[e[pos][i]][1]+1<<endl;
			dyc*=(dp[e[pos][i]][0]+dp[e[pos][i]][1]+1)%mod;
			dyc%=mod;
		}
	}
	dp[pos][1]+=dyc;
	dp[pos][1]%=mod;
	for(int i = 0;i<e[pos].size();i++){
		if(e[pos][i]!=fa[pos]){
			g[e[pos][i]] = dp[pos][1]*qpow(dp[e[pos][i]][1]+dp[e[pos][i]][0]+1,mod-2)%mod+1;
		}
	}
	return;
}
void dfs2(int pos){
	if(fa[pos]!=1){
		g[pos]*=g[fa[pos]];
		g[pos]%=mod;
	}
	for(int i = 0;i<e[pos].size();i++){
		if(e[pos][i]!=fa[pos]){
			dfs2(e[pos][i]);
		}
	}
	return;
}
signed main(){
	cin>>n;
	for(int i = 1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i = 1;i<=n;i++){
		dp[i][0] = 0;
		dp[i][1] = 0;
	}
	dfs(1);
	dfs2(1);
//	for(int i = 1;i<=n;i++){
//		cout<<g[i]<<" ";
//	}
//	cout<<endl;
	cin>>m;
	for(int i = 1;i<=m;i++){
		int pos;
		cin>>pos;
		cout<<(dp[1][0]+dp[1][1]+mod-g[pos]*(dp[pos][0]+dp[pos][1])%mod)%mod<<endl;;
	}
	return 0;
}