某岛

… : "…アッカリ~ン . .. . " .. .
August 26, 2016

树形 DP

  • 直径
  • 点覆盖集
  • 路径覆盖
  • 支配集

难度:2
前提:动态规划
后继:

资料:

  • https://cses.fi/problemset/task/1133

    #include <lastweapon/io>
    
    using namespace lastweapon;
    
    const int N = int(2e5) + 9;
    
    int n, h[N]; LL f[N], g[N];
    VVI v;
    
    void dfs1(int r, int p = -1) {
        for(int& a : v[r]) if (a != p) {
            dfs1(a, r);
            h[r] += h[a];
            f[r] += f[a] + h[a];
        }
        h[r]++;
    }
    
    void dfs2(int r, int p = -1) {
        for(int& a : v[r]) if (a != p) {
            g[a] = (f[r] - (f[a] + h[a])) + g[r] + (n - h[a]);
            dfs2(a, r);
        }
    }
    
    int main() {
    
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
    #endif
    
        RD(n);
        v.resize(n);
        int a, b;
        while(cin >> a >> b) {
            v[a-1].PB(b-1);
            v[b-1].PB(a-1);
        }
        dfs1(0);
        dfs2(0);
        REP(i, n) printf("%lld ", f[i] + g[i]);
    }
    
    

  • https://usaco.guide/problems/ac-subtree/solution

    #include <lastweapon/io>
    #include <lastweapon/number>
    
    using namespace lastweapon;
    
    const int N = int(1e5) + 9;
    
    VI adj[N]; Int f[N], fl[N], fr[N], g[N];
    int n;
    
    void dfs1(int u = 0, int p = -1) {
        f[u] = 1;
        for(auto& v: adj[u]) if (v != p) {
            dfs1(v, u);
            fl[v] = f[u];
            f[u] *= f[v] + 1;
        }
        f[u] = 1;
        for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
            int v = *it; if (v == p) continue;
            fr[v] = f[u];
            f[u] *= f[v] + 1;
        }
    }
    
    void dfs2(int u = 0, int p = -1) {
        for(auto& v: adj[u]) if (v != p) {
            g[v] = (g[u] + 1) * fl[v] * fr[v]; //f[u] / (f[v] + 1);
            dfs2(v, u);
        }
    }
    
    int main() {
    
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
    #endif
    
        RD(n, MOD); DO(n - 1) {
            int a, b; RD(a, b); --a; --b;
            adj[a].PB(b);
            adj[b].PB(a);
        }
    
        dfs1(); dfs2();
    
        REP(i, n) printf("%d\n", f[i] * (g[i] + 1));
    }
    
    

  • https://codeforces.com/contest/1187/problem/E

    
    

习题: