礼物 换根dp

题目大意

有一棵n( $n\le 1e6n\; \backslash leq\; 1e6$ )个节点的树 , 要求找到一个根使得下面等式最大 .

解题思路

换根DP , 因为每次我们都可以考虑把子节点换成根节点 , 转移是比较方便的 . 首先我们先找一个点作为根节点算出贡献 . 为了避免重复计算带来的麻烦 , 我先计算 的情况 , 最后乘上2再加上 $i=ji\; =\; j$ 的情况 . 当然其他方法也可以 , 只要考虑相关转移方式就好了 .

我们考虑根节点从当前根节点u转移到其中一个子节点v , 子节点v的子树部分的所有LCS都不会改变 , 其他子树内部的LCS也不会有改变 , 跟父节点的答案值区别在于v以及其子树的节点和父节点及其他子树节点之间的LCS发生改变 , 由父节点u变化为v, 于是只需要一次转移 .

由于需要预先知道父节点的DP值 , 所以须先更新自身节点 , 然后再遍历其子节点 . 转移方程

参考代码

//InzamZ
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define F(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define FIO std::ios::sync_with_stdio(false);\
            std::cin.tie(0)
#define FFFOUT freopen("./out.txt" , "w", stdout)
#define FFFIN freopen("./in.txt" , "r", stdin)
const int maxn = 1e6 + 10;
const int maxb = 110;
int T = 1, n, m, ansx, ans = 0, siz[maxn], dp[maxn];
vector<int>e[maxn], v;
string s;

int dfs1(int u, int fa) {
    int soncnt = 1, tmp;
    for (auto x : e[u]) {
        if (x == fa)
            continue;
        tmp = dfs1(x, u);
        dp[u] += u * soncnt * tmp;
        dp[u] += dp[x];
        soncnt += tmp;
    }
    siz[u] = soncnt;
    return soncnt;
}

int dfs2(int u, int fa) {
    if (u != 1)
        dp[u] =  (u - fa) * (n - siz[u]) * siz[u] + dp[fa];
    for (auto x : e[u]) {
        if (x == fa)
            continue;
        dfs2(x, u);
    }
    return 0;
}

int solve() {
    ans = 0;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i) {
        if (dp[i] > ans) {
            ans = dp[i];
            ansx = i;
        }
    }
    cout << ansx << ' ' <<  ans * 2 + (n + 1) * n / 2 << '\n';
    return 0;
}

signed main() {
    FIO;
    while (T--) {
        // cout << "Case #" << T + 1 << ":" << endl;
        solve();
    }
    return 0;
}