[ARC230A] Meeting on Tree

· · 题解

或许更好的阅读体验。

这题 *900？？？骗鬼呢？？？

思路：

考虑一条边的贡献，枚举左右两边分别选了多少点，显然有：

\sum_{u} \sum_{i = 0}^{siz_u} \sum_{j = 0}^{n - siz_u} \min(i ,j) \binom{siz_u}{i} \binom{n - siz_u}{j}

显然枚举 u 是必要的，考虑怎么快速算后面的式子，即：

\begin{aligned} LHS &= \sum_{i \le x} \sum_{j \le y} \min(i, j) \binom{x}{i} \binom{y}{j} \\ &= \sum_{i \le x} i \binom{x}{i} \sum_{j \ge i} \binom{y}{j} + \sum_{j \le y} j \binom{y}{j} \sum_{i > j} \binom{x}{i} \\ &= x \sum_{i \le x - 1} \binom{x - 1}{i} \sum_{j \ge i + 1} \binom{y}{j} + y \sum_{j \le y - 1} \binom{y - 1}{j} \sum_{i > j + 1} \binom{x}{i} \\ &= x \sum_{i \le x - 1} \binom{x - 1}{i}(S_{y, y} - S_{y, i}) + y \sum_{j \le y - 1} \binom{y - 1}{j} (S_{x, x} - S_{x, j + 1})\end{aligned}

你发现难点在于 \sum_{i \le x'} \binom{x'}{i} \sum_{j \le i} \binom{y'}{j} 这种类型式子上，先反转下标转化成 i + j 的限制，考虑枚举 k = i + j，然后范德蒙雷卷积，那么：

\begin{aligned} LHS &= \sum_{i \le x'} \binom{x'}{i} \sum_{j \le i} \binom{y'}{j} \\ &= \sum_{i \le x'} \binom{x'}{i}\sum_{y'\le i +j} \binom{y'}{y' - j} \\ &=\sum_{k \ge y'} \sum_i \binom{x'}{i} \binom{y'}{k - i} \\ &= \sum_{k \ge y'} \binom{x' + y'}{k} \end{aligned}

而 x' + y' = n - 1 是定值，预处理它的后缀和即可，时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 3e5 + 10, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
} 
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int n, ans;
int siz[N], fac[N], ifac[N], p2[N], s[N];
vector<int> E[N];
inline void add(int u, int v){
    E[u].push_back(v);
    E[v].push_back(u);
}
inline void init(){
    fac[0] = fac[1] = p2[0] = 1, p2[1] = 2;
    for(int i = 2; i < N; ++i){
        fac[i] = 1ll * fac[i - 1] * i % mod;
        p2[i] = 2ll * p2[i - 1] % mod;
    }
    ifac[N - 1] = qpow(fac[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; --i)
      ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
}
inline int binom(int n, int m){
    if(m > n)
      return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline void solve(int x, int y){
    // getadd(ans, 1ll * x * p2[x - 1] % mod * p2[y] % mod);
    // getadd(ans, 1ll * y * p2[y - 1] % mod * p2[x] % mod);
    // int s1 = 0, s2 = 0;
    // for(int i = 0; i < x; ++i)
    //   for(int j = 0; j < i + 1; ++j)
    //     getadd(s1, 1ll * binom(x - 1, i) * binom(y, j) % mod);
    // for(int j = 0; j < y; ++j)
    //   for(int i = 0; i < j + 2; ++i)
    //     getadd(s2, 1ll * binom(y - 1, j) * binom(x, i) % mod);
    // cerr << x << ' ' << y << ' ' << s1 << ' ' << s2 << '\n';
    // cerr << s[y] << ' ' << s[x - 1] << '\n';
    // s1 = 1ll * x * s1 % mod, s2 = 1ll * y * s2 % mod;
    // getdec(ans, s1);
    // getdec(ans, s2);
    // cerr << x << ' ' << y << '\n';
    // for(int i = 0; i <= x; ++i)
    //   for(int j = 0; j <= y; ++j)
    //     getadd(ans, 1ll * min(i, j) * binom(x, i) % mod * binom(y, j) % mod);
    // cerr << binom(y, 1) << '\n';
    getadd(ans, 1ll * x * p2[x - 1] % mod * p2[y] % mod);
    getadd(ans, 1ll * y * p2[y - 1] % mod * p2[x] % mod);
    getdec(ans, 1ll * x * s[y] % mod);
    getdec(ans, 1ll * y * s[x - 1] % mod);
}
inline void dfs(int u, int fa){
    siz[u] = 1;
    for(auto v : E[u]){
        if(v == fa)
          continue;
        dfs(v, u);
        siz[u] += siz[v];
        solve(siz[v], n - siz[v]);
    }
}
int main(){
    init();
    n = read();
    for(int u, v, i = 1; i < n; ++i){
        u = read(), v = read();
        add(u, v);
    }
    for(int i = n - 1; i >= 0; --i){
        s[i] = s[i + 1];
        getadd(s[i], binom(n - 1, i));
    }
    dfs(1, 1);
    write(ans);
    return 0;
}