题解：P9648 [SNCPC2019] Unrooted Trie
_gghack_
·
·
题解
前言：
我是入机，模拟赛题解看不懂一点，最后学了 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.
当把子树搜完之后，记得还原最初的 $\text{dp}$ 数表的值，不然会影响到下次换根。
```cpp
// 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:添加了对"入机"一词的解释，免得被认为是错别字。