Accumulation Degree

传送戳我

解题思路

根据题目意思，结合图中信息，统计每个节点的度，记为dep数组，并建立一棵以1为根节点的树。
我们通过一次dfs(1,0)统计到以1为根节点，题目所求的最大积累度。
如果这个的子节点是叶子节点，那么
否则，
这个过程我们需要先找到最底层叶子节点向上推，所以 dfs的地方别写错了
后面我们考虑换根之后值的变化，如果这个节点 原先只有一棵子树，那么换根之后就变成叶子节点了所以他的子节点对应f数组直接为
否则，节点 存在多个子树，以其中一个子节点v，作为新的树根的话,w为两节点边权，对节点u来说，少了来自v的那一部分来源，对于v来说，多了一份来自u的来源，所以得到
注意着是从以1为根的子节点一步步向下推，需要得到父节点才可以算出子节点，dfs地方别写错了

时间复杂度 O( )

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 2e5 + 7;
vector<pair<int, int> > tr[N];
int d[N], f[N], dep[N];

void dfs1(int u, int fa) {
    for (int i = 0; i < tr[u].size(); ++i) {
        int v = tr[u][i].first, w = tr[u][i].second;
        if (v == fa)    continue;
        dfs1(v, u); //自底向上求得d数组
        if (dep[v] == 1)    d[u] += w;
        else    d[u] += min(w, d[v]);
    }
}

void dfs2(int u, int fa) {
    for (int i = 0; i < tr[u].size(); ++i) {
        int v = tr[u][i].first, w = tr[u][i].second;
        if (v == fa)    continue;
        if (dep[u] == 1)    f[v] = d[v] + w;
        else    f[v] = d[v] + min(w, f[u] - min(w, d[v]));
        dfs2(v, u); //自顶向下求得换根后的f数组
    }
}

int main() {
    int T = read();
    while (T--) {
        memset(dep, 0, sizeof(dep));
        memset(d, 0, sizeof(d));   // +_+!!!一定要记得初始化吖
        memset(f, 0, sizeof(f));
        for (int i = 0; i < N; ++i)    tr[i].clear();
        int n = read();
        for (int i = 1; i < n; ++i) {
            int u = read(), v = read(), w = read();
            tr[u].push_back(make_pair(v, w)); ++dep[u];
            tr[v].push_back(make_pair(u, w)); ++dep[v];
        }
        dfs1(1, 0);
        f[1] = d[1];
        dfs2(1, 0);
        printf("%d\n", *max_element(f + 1, f + 1 + n));
    }
    return 0;
}

树学

解题思路

至于这道题，我当时比赛后补题是通过找重心的办法，其实也可以用上面换根的思想来实现，不过这题符合 的概念，直接找到重心，以重心为根dfs一遍就行了，不需要上方那样多次换根DP。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int maxn = 1e6 + 7;
vector<int> tree[maxn];
int n, minNode, minBalance;
//minNode当前重心节点
//minBalance当前重心节点的最大子树节点个数
int d[maxn], deep[maxn];
//d[i]表示以i为根的子树节点个数

void dfs1(int u, int fa) {
    d[u] = 1; //节点本身
    int maxSub = 0, size = tree[u].size(); //maxSub为节点u的最大子树节点个数
    for (int i = 0; i < size; i++) {
        int v = tree[u][i];
        if (v != fa) {
            dfs1(v, u);
            d[u] += d[v];
            maxSub = max(maxSub, d[v]);
        }
    }
    maxSub = max(maxSub, n - d[u]);
    if (maxSub < minBalance) {
        minNode = u;
        minBalance = maxSub;
    }
}

void dfs2(int u, int fa) {
    int size = tree[u].size();
    for (int i = 0; i < size; ++i) {
        int v = tree[u][i];
        if (v == fa)    continue;
        deep[v] = deep[u] + 1;
        dfs2(v, u);
    }
}

int main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    minNode = 0; minBalance = 0x3f3f3f3f;
    dfs1(1, 0);
    dfs2(minNode, 0);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) ans += deep[i];
    printf("%lld\n", ans);
    return 0;
}