题解：CF2183F Jumping Man

· · 题解

这里介绍不用转成 dfn 的做法。

有一个经典的转化就是你求次数的平方和等价于选择两个字符串相等的方案数。

显然是要动态规划，我们设 f_{u,v} 为分别从 u, v 开始向子树走，能走出相同串的方案数。

首先有显然的转移。

f(u, v) = [s_u = s_v] \times \left( 1 + \sum_{x \in \text{subtree}(u) \setminus \{u\}} \sum_{y \in \text{subtree}(v) \setminus \{v\}} f(x, y) \right)

考虑怎么优化，我们可以考虑下实际意义，就是你要从 u 子树中随便挑个点 x，从 v 子树中随便挑个点 y，求和 f_{x, y}。我们可以设计 g(u, v) 为 \sum_{x \in \text{subtree}(u)} \sum_{y \in \text{subtree}(v)} f(x, y)。

还有 H(u, v) 就是左边所有点去和 v 单点匹配。

H(u, v) = \sum_{a \in \text{subtree}(u)} f(a, v)

显然有：

H(u, v) = f(u, v) + \sum_{x \in \text{son}(u)} H(x, v)

有了 H 我们 g 就好转移了。

G(u, v) = H(u, v) + \sum_{y \in \text{son}(v)} G(u, y) f(u, v) = [s_u = s_v] \times \left( 1 + \sum_{x \in \text{son}[u]} \sum_{y \in \text{son}[v]} G(x, y) \right)

注意转移顺序按照后序遍历即可。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
typedef long long ll;
using namespace std;
const int N = 5000 + 10;
const int P = 998244353;
int n; char s[N];
int head[N], nxt[N << 1], to[N << 1], E;
inline void add(int x, int y)
{
    nxt[E] = head[x]; to[E] = y; head[x] = E ++;
}
vector<int> q; int F[N];
void dfs(int u, int fa)
{
    F[u] = fa;
    for(int i = head[u]; ~i; i = nxt[i])
    {
        int x = to[i];
        if(x == fa) continue;
        dfs(x, u);
    }
    q.push_back(u);
}
ll f[N][N], g[N][N], h[N][N];
int main()
{
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T -- )
    {
        cin >> n; E = 0; memset(head, -1, sizeof head); q.clear();
        rep(i, 1, n) cin >> s[i];
        rep(i, 1, n - 1)
        {
            int x, y; cin >> x >> y; add(x, y), add(y, x);
        }
        dfs(1, -1);
        rep(i, 1, n) rep(j, 1, n) f[i][j] = g[i][j] = h[i][j] = 0;
        for(auto u : q) for(auto v : q)
        {
            if(s[u] == s[v])
            {
                ll sm = 1; 
                for(int i = head[u]; ~i; i = nxt[i]) for(int j = head[v]; ~j; j = nxt[j])
                {
                    if(to[i] == F[u] || to[j] == F[v]) continue;
                    int x = to[i], y = to[j]; sm += g[x][y]; if(sm>P) sm-=P;
                }
                f[u][v] = sm;
            } h[u][v] = f[u][v];
            for(int i = head[u]; ~i; i = nxt[i]) if(to[i] != F[u])
            {
                int x = to[i]; h[u][v] += h[x][v]; if(h[u][v] > P) h[u][v] -= P;
            } g[u][v] = h[u][v];
            for(int i = head[v]; ~i; i = nxt[i]) if(to[i] != F[v])
            {
                int y = to[i]; g[u][v] += g[u][y]; if(g[u][v]>P) g[u][v]-=P;
            }
        }
        rep(i, 1, n) cout << g[i][i] << ' ';
        cout << '\n';
    }
    return 0;
}