自动搬运

查看原文

来自洛谷，原作者为

	gghack_Nythix ‎

搬运于2025-08-24 22:50:25，当前版本为作者最后更新于2024-10-14 15:40:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言：

我是入机，模拟赛题解看不懂一点，最后学了 zjh 大佬做法也是一看就懂了。

分析：

可以考虑换根 $\text{dp}$。设 $dp_i$ 表示以 $i$ 为根的子树中有没有重复的，那么首先判掉一定无解的情况：

• 同层有两个及以上的相同字符。

把这个判掉之后还要考虑：

• 他的儿子里面是否有重复的。

那么 $\text{dp}$ 方程也就自然而然的出来了。

$$dp_{now} = \left\{\begin{matrix} 0& \exists s_{x\in{son}} > \text{2} \\ \min_{} \{dp_{x\in{son}}\} & \text{otherwise} & \end{matrix}\right. $$

$son$ 表示 $now$ 的儿子集合。

当把子树搜完之后，记得还原最初的 $\text{dp}$ 数表的值，不然会影响到下次换根。

// EXpert实力！
# include <bits/stdc++.h>
# define pb push_back
# define cl clear
using namespace std;
const int N = 2e5 + 5;
int n;
struct node {
	int v;
	char w;
};
vector <node> g[N] ;
int vec[N],cnt;//vec记录方案
int mp[N][27];
bool dp[N];
void pre_dfs (int now , int fa) {
	dp[now] = 1; 
	for (auto x : g[now]) {
		if (x.v == fa) continue; 
		pre_dfs (x.v , now);
		dp[now] &= dp[x.v];
		mp[now][x.w - 'a'] ++;
	}
	for (int i = 0;i < 26;++i) if (mp[now][i] > 1) dp[now] = 0;
}
void cgroot (int now , int fa , int op ,int EX, int pert, char pre) {
	mp[now][pre - 'a'] += op, mp[fa][pre - 'a'] -= op;
	dp[now] = dp[fa] = 1;
	if (op == -1) return dp[now] = EX , dp[fa] = pert,void();
	for (int i = 0;i < 26;++i) {
		if (mp[now][i] > 1) dp[now] = 0;
		if (mp[fa][i] > 1) dp[fa] = 0;
	}
	for (auto x : g[fa]) if (x.v != now) dp[fa] &= dp[x.v];
	for (auto x : g[now]) dp[now] &= dp[x.v];		
	if (dp[now] && op == 1) vec[++cnt] = now;
}
void dfs (int now,int fa ,char pre) {
	int EX = dp[now],pert = dp[fa];
	if (now != 1) cgroot(now , fa , 1 ,EX , pert ,pre);
	for (auto x : g[now]) if (x.v != fa) dfs (x.v , now , x.w);
	if (now != 1) cgroot (now , fa , -1 ,EX , pert , pre);
}
void solve () {
	bool Lian = 1;
	cnt = 0;
	cin >> n;
	memset (dp,0,sizeof dp);
	memset (mp,0,sizeof mp);
	for (int i = 1;i <= n;++i) g[i].cl();
	for (int i = 1;i < n;++i) {
		int u,v; char w;
		cin >> u >> v >> w , g[u].pb(node {v,w} ) , g[v].pb(node {u,w} );
	}
	pre_dfs (1 , -1);
	if (dp[1]) ++cnt;
	dfs (1 , -1 , -1);
	cout << cnt << "\n";
	return void();
}
signed main () {
	ios::sync_with_stdio(false);
	cin.tie (0);
	cout.tie (0);
	int T;
	cin >> T;
	while (T -- >0) solve ();
	return 0;
}
/*
5
1 2 a
1 3 a
3 4 b
4 5 c
*/

upd:添加了对"入机"一词的解释，免得被认为是错别字。