计算特定条件下树的公共祖先的深度和

蟠桃树【算法赛】

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
using pii = pair<int, int>;
vector<int>tr[100005];

int n;
string s;
int ans;
int cnt[100005][2];

void dfs(int x, int fa, int dep) {
	cnt[x][s[x] - '0'] = 1;//对应颜色赋值
	for (auto t : tr[x]) {
		dfs(t, x, dep + 1);//一直往下走
		ans = (ans + cnt[x][0] * cnt[t][1] * dep) % mod;//计算贡献
		ans = (ans + cnt[x][1] * cnt[t][0] * dep) % mod;

		cnt[x][0] += cnt[t][0];//更新根节点的黑色
		cnt[x][1] += cnt[t][1];//更新根节点的白色

	}

}


signed main() {
	cin >> n;
	cin >> s;
	s = " " + s;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		if (u > v) swap(u, v);
		tr[u].push_back(v);
	}

	dfs(1, 0, 1);
	cout << ans;


}