[HDU6647] Bracket Sequences on Tree 题解
一道纯靠自己推出来的换根\(dp+\)树哈希，写篇题解庆祝一下~~
题意：给定一棵无根树，你可以任意选择根节点和遍历顺序，每次遍历时进入一个节点就标记一个(，离开一个节点就标记一个)，问所有存在的括号序列有多少种，对998244353取模。
先考虑根固定的情况如何统计答案。
容易发现两个序列形态相同当且仅当两棵树形态相同。这个玩意可以用树\(Hash\)维护。根据乘法原理，容易知道对于一个点\(x\)，以及它的儿子 \(y\) ，其贡献 \(res_x=\prod_{}res[y]\).由于遍历顺序不固定，因此实际对答案的贡献要乘上 \((deg_x-1)!\) .但是考虑有重复子树的情况。根据全排列知识，我们计每一个 \(y\) 形态的出现次数是 \(num_i\)，则 \(res_x=\prod_{}res[y]\times \frac{(deg_x-1)!}{\sum num_i!}\).
那么现在考虑换根。在第二次遍历中，根据换根 \(dp\) 的一般形式，我们令当前在 \(x\) 节点，我们要更新其儿子节点 \(y\) 的贡献。具体地，我们考虑记录每个点 \(x\) 成为根节点时它的所有子节点形态的个数 \(mp[x][y]\)，按照套路先算出以 \(x\) 为根节点时除去 \(y\) 的子树部分的贡献 \(kes\)，再用它更新 \(y\) 点的最终答案。
根据上面的基础式子，我们容易推出：
\[kes=\frac{res_x\times mp[x][Hs_y]}{res_y\times deg_x} \]其中 \(Hs_y\) 是以1为根时的 \(y\) 子树 \(Hash\) 值。
然后我们计算出根据题单里前几道题的套路以 \(x\) 为根节点时除去 \(y\) 的子树部分的\(Hash\) 值 \(ks\)，并更新 \(Hs_y\) 为 \(y\) 为根时的 \(Hash\) 值。最后将 \(ks\) 加入 \(y\) 的桶里，并计算出新的 \(res_y\).
\[res_y=\frac{res_y\times kes\times deg_y}{mp[y][ks]} \]详情见代码。
#include <bits/stdc++.h>
#define mod 998244353
#define N 100005
#define ull unsigned long long
#define int long long
using namespace std;
int fac[N];
int T;
int n;
struct Node {
int to, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
mt19937 XYCYX(time(0));
const ull mask = XYCYX();
ull shift(ull x) {
x ^= mask;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x ^= mask;
return x;
}
ull Hs[N];
int res[N];
int inv[N];
int INV[N];
int deg[N];
unordered_map<ull, int>mp[N];
void dfs1(int x, int fa) {
Hs[x] = res[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if (y == fa)
continue;
dfs1(y, x);
Hs[x] += shift(Hs[y]);
mp[x][Hs[y]]++;
res[x] = res[x] * res[y] % mod;
}
if (x != 1)
res[x] = res[x] * fac[deg[x] - 1] % mod;
else
res[x] = res[x] * fac[deg[x]] % mod;
for (auto it : mp[x])
res[x] = res[x] * inv[it.second] % mod;
}
void dfs2(int x, int fa) {
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if (y == fa)
continue;
int kes = res[x] * mp[x][Hs[y]] % mod * qpow(res[y], mod - 2) % mod * qpow(deg[x], mod - 2) % mod;
ull ks = Hs[x] - shift(Hs[y]);
mp[y][ks]++;
Hs[y] = Hs[y] + shift(Hs[x] - shift(Hs[y]));
res[y] = res[y] * kes % mod * deg[y] % mod * INV[mp[y][ks]] % mod;
dfs2(y, x);
}
}
unordered_map<ull, int>MP;
int u[N], v[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
fac[0] = inv[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = qpow(fac[i], mod - 2);
INV[i] = qpow(i, mod - 2);
}
while (T--) {
cnt = 0;
for (int i = 0; i <= n; i++) {
e[i].to = e[i].nxt = e[i * 2].to = e[i * 2].nxt = 0;
head[i] = head[i * 2] = 0;
Hs[i] = 0;
res[i] = 0;
deg[i] = 0;
mp[i].clear();
}
MP.clear();
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
u[i] = x, v[i] = y;
add(x, y);
add(y, x);
deg[x]++;
deg[y]++;
}
dfs1(1, 0);
dfs2(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++)
MP[Hs[i]] = res[i];
for (auto i : MP)
ans = (ans + i.second) % mod;
cout << ans << "\n";
}
return 0;
本题的难点：
-
灵活运用排列组合相关知识，计算根固定时的答案贡献。
-
熟练掌握换根 \(dp\) 的 $\ up-down\ $思想推出转移式并进行一定程度上的转化。
-
各种繁琐细节的处理！
\(End.\)
标签：Hs,int,题解,Tree,Bracket,mp,res,deg,mod From： https://www.cnblogs.com/Rock-N-Roll/p/18059865