换根DP

比较复杂，后面有空再加点注释。

具体使用方式：代码：solution2部分
来源也是官方题解视频：公式解説(Youtube)

struct RerootDP {
    struct DP {
        DP() {}
        DP operator+(const DP &rhs) const {
            // edit here
        }
        DP add_root() const {
            // edit here
        }
    };

    int n;
    std::vector<std::vector<int>> g;
    std::vector<std::vector<DP>> dp;
    std::vector<DP> ans;
    RerootDP(int n = 0): n(n), g(n), dp(n), ans(n) {}
    void add(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);  
    }
    void init() {
        dfs(0);
        bfs(0);
    }
    DP dfs(int u, int p = -1) {
        DP dpsum;
        dp[u] = std::vector<DP>(g[u].size());
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (v == p) continue;
            dp[u][i] = dfs(v, u);
            dpsum = dpsum + dp[u][i];
        }
        return dpsum.add_root();
    }
    void bfs(int u, const DP &dpp = DP(), int p = -1) {
        int deg = g[u].size();
        for (int i = 0; i < deg; ++i) {
            if (g[u][i] == p) {
                dp[u][i] = dpp;
            }
        }
        std::vector<DP> dpsumL(deg + 1), dpsumR(deg + 1);
        for (int i = 0; i < deg; ++i) {
            dpsumL[i + 1] = dpsumL[i] + dp[u][i];
        }
        for (int i = deg - 1; i >= 0; --i) {
            dpsumR[i] = dpsumR[i + 1] + dp[u][i];
        }
        ans[u] = dpsumL[deg].add_root();
        for (int i = 0; i < deg; ++i) {
            int v = g[u][i];
            if (v == p) continue;
            DP d = dpsumL[i] + dpsumR[i + 1];
            bfs(v, d.add_root(), u);
        }
    }
};