树学

https://ac.nowcoder.com/acm/problem/201400
先看这道树学题
如果有了解过树的重心，那么这道题就easy了，无非就是找树的重心。
找树的重心就是一遍dfs。然后再一遍dfs求每个点的深度。相加即可。

代码

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
vector<int> tree[maxn];
ll n, minNode, minBalance;
//minNode当前重心节点
//minBalance当前重心节点的最大子树节点个数 
ll d[maxn], dep[maxn];
//d[i]表示以i为根的子树节点个数 
void dfs(int u,int fa){
    d[u]=1; //节点本身 
    ll maxSub = 0,size = tree[u].size(); //maxSub为节点u的最大子树节点个数 
    for(int i = 0; i < size; i++){
        int v = tree[u][i];
        if(v != fa){
            dfs(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 dfs1(int u, int fa){
    int size = tree[u].size();
    for(int i = 0; i < size; i++){
        if(tree[u][i] == fa) continue;
        dep[tree[u][i]] = dep[u]+1;
        dfs1(tree[u][i], u);
    }
}
int main(){
    scanf("%d",&n);
    memset(d, 0, sizeof(d));
    for(int i = 1;i < n; i++){
        int u,v;
        scanf("%d%d",&u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    minNode = 0; minBalance = 0x3f3f3f3f;
    dfs(1, 0);
    dfs1(minNode, 0);
    ll ans=0;
    for(int i = 1; i <= n; i++){
        ans += dep[i];
    }
    printf("%lld",ans);
    return 0;
}

然后是第二道题

这题是一道很经典的换根dp。
分析：设d[x]表示在以x为根的子树中，把x作为源点的最大流量，这个方程很简单，d[x]=∑min(d[son],w(x,son))，当son为叶子节点时，d[x]=d[x]+w(x,y)，这样可以算出以其中一个点为源点时的最大流量，但是我们要计算以每个点为源点的最大值，朴素想法当然是枚举每个点计算。这里我们可以用二次扫描与换根法代替源点的枚举，设f[x]表示把x作为源点时，整个水系的最大流量，于是我们可以通过d来计算f。显然f[root]=d[root]，若想把根从x变为y，
f[y]=min(d[x]-min(d[y],w(x,y)),w(x,y))，当x为叶子节点时f[y]=f[x]+w(x,y)。

代码

#include <bits/stdc++.h>
#include <cstdio>
#include <string>
#include <cstring>
#define N 400005
using namespace std;

struct arr
{
    int to, nxt, w;
}a[N];
int f[N],d[N],du[N],ls[N*2],l,n,T;
bool v[N];

void add(int x, int y, int z)
{
    a[++l].to = y;
    a[l].nxt = ls[x];
    a[l].w = z;
    ls[x] = l;
}

int min(int x, int y){return x<y?x:y;}

void dp(int x)
{
    v[x] = true;
    for (int i = ls[x]; i; i = a[i].nxt)
        if (!v[a[i].to])
        {
            dp(a[i].to);
            d[x]+=du[a[i].to]==1?a[i].w:min(d[a[i].to],a[i].w);
        }
}

void dfs(int x)
{
    v[x] = true;
    for (int i = ls[x]; i; i = a[i].nxt)
        if (!v[a[i].to])
        {
            //f[a[i].to] = d[a[i].to] + du[x]==1?a[i].w:min(f[x] - min(d[a[i].to],a[i].w),a[i].w);
            if (du[x] == 1) f[a[i].to] = d[a[i].to] + a[i].w;
                else f[a[i].to] = d[a[i].to] +min(f[x] - min(d[a[i].to],a[i].w),a[i].w);
            dfs(a[i].to);
        }
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            v[i] = false;
            f[i] = d[i] = du[i] = 0;
        }
        memset(ls, 0, sizeof(ls));
        l = 0;
        for (int i = 1; i < n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
            du[x]++;
            du[y]++;
        }
        dp(1);
        for (int i = 1; i <= n; i++)
            v[i] = false;
        f[1] = d[1];
        dfs(1);
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (f[i] > ans) ans = f[i];
        printf("%d\n", ans);
    }
}