树形DP

dp[u][0] += dp[to][1];
dp[u][1] += min(dp[to][1], dp[to][0]);

对任意一条链，「链上的节点」和「与该链直接相连且不在链上的节点」构成一条「毛毛虫」。
求树上「毛毛虫」节点数的最大值。

参考

#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 300010;

struct node
{
    int to, next;
} e[maxn<<1];
int head[maxn<<1], tot;
int size[maxn], ans;

void add(int u, int v )
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

void dfs1(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = sizej = 0;
    //printf("%d %d\n", from, fa);
    for ( int i = head[from]; i; i = e[i].next )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs1(to, from);
        sizei = max(sizei, size[to]);
    }
    if ( deg == 1 ) size[from] = sizei + 1;
    else size[from] = sizei + deg - 1;
}

void dfs2(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = sizej = 0;
    for ( int i = head[from]; i; i = e[i].next )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs2(to, from);
        if ( size[to] > sizei ) { sizej = sizei; sizei = size[to]; }
        else if ( size[to] > sizej ) sizej = size[to];
    }
    if ( sizei == 0 ) ans = max( ans, deg + 1 );
    else if ( sizej == 0 ) ans = max( ans, sizei + deg );
    else ans = max(ans, sizei + sizej + deg - 1);
}

void dfs3(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = 0, sizej = 0;
    for ( int i = head[from]; i; i = e[i].next  )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs3(to, from);
        if ( size[to] > sizei ) { sizej = sizei; sizei = size[to]; }
        else if ( size[to] > sizej ) sizej = size[to];
    }

    if ( sizei == 0 ) ans = max( ans, deg + 1 );
    else if ( sizej == 0 ) ans = max( ans, sizei + deg );
    else ans = max(ans, sizei + sizej + deg - 1);

    if ( deg == 1 ) size[from] = sizei + 1;
    else size[from] = sizei + deg - 1;
}

int main()
{
    ans = 0;
    scanf("%d %d", &n, &m);
    int from, to;
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    /*dfs1(1, 0);
    dfs2(2, 0);*/
    dfs3(1, 0);
    printf("%d\n", ans);

    return 0;
}

#include <bits/stdc++.h>
// 注意分析多种情况出现时子树的形状
using namespace std;

const int maxn = 100010;
const int INF = 0x3f3f3f3f;

struct node
{
    int to, next;
} e[maxn<<1];

int head[maxn], tot, n;
int times[maxn], val[maxn];
int f[maxn], flag = 0;

void add(int u, int v)
{
    e[++tot] = node{v,head[u]};
    head[u] = tot;
}

void dfs( int u, int fa )
{
    priority_queue<int> q;
    for ( int i = head[u]; i; i = e[i].next )
    {
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs(to, u);
        q.push(f[to]);
    }
    int cnt = 0, jil = INF; 
    int xx;
    if ( q.size() >= 2 )
    {
        xx = q.top();q.pop();
        jil = q.top();q.push(xx);
    }
    while ( !q.empty() )
    {
        cnt ++;
        xx = q.top();
        if ( xx == 0 || ( times[u] == cnt && jil == xx ) ) flag = 1;
        if ( xx < 0 || times[u] + 1 == cnt  ) break;
        f[u] += xx;
        jil = xx;
        q.pop();
    }
}

int main()
{
    scanf("%d", &n);
    for ( int i = 2; i <= n; i ++ ) scanf("%d", &val[i]);
    for ( int i = 2; i <= n; i ++ ) 
    {
        scanf("%d", ×[i]);
        times[i] --;
    }
    dfs(1, 0);
    times[1] = INF;val[1] = 0;
    int from, to;
    for ( int i = 1; i <= n - 1; i ++ )
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    for ( int i = 1; i <= n; i ++ ) f[i] = val[i];
    dfs(1, 0);
    //for ( int i = 1; i <= n; i ++ )
    printf("%d\n", f[1]);
    if ( flag )  printf("solution is not unique\n");
    else printf("solution is unique\n");
    return 0;
}

dp[u]为以u为根的树,每个人装好电脑且遍历完的时间(不包括回来)
g[u]为以u为根的树,遍历(一次)完的时间
dp[u]-g[u]为等待时间,且从大到小排序,因为一棵树的总操作时间取决于这棵树的所有子树中操作时间最长的那一棵

转移方程:
dp[u] = max(dp[u], dp[sons] + g[u] + 1);
g[u] += (g[sons] + 2);
可以认为dp[sons]是进入子树,g[u]是从子树回来,加一是从 u 到 sons.

    #include <bits/stdc++.h>

using namespace std;

const int maxn = 500010;

struct node
{
    int to, next;
} e[maxn<<1];

int n;
int c[maxn], head[maxn], tot;
int dp[maxn], g[maxn];

void add( int u, int v )
{
    e[++tot] = node{v,head[u]};
    head[u] = tot;
}

bool cmp(int a, int b)
{
    return dp[a] - g[a] >  dp[b] - g[b] ;
}

void dfs(int u, int fa)
{
    if (u != 1) dp[u] = c[u];
    vector<int> son;
    for (int i = head[u]; i; i = e[i].next)
    {
        int to = e[i].to;
        if ( to == fa ) continue;
        son.push_back(to);
        dfs(to, u);
    }
    sort(son.begin(), son.end(), cmp);
    for (auto ite : son)
    {
        int sons = (int) ite;
        dp[u] = max(dp[u], dp[sons] + g[u] + 1);
        g[u] += (g[sons] + 2);
    }

}

int main()
{
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    int from, to;
    for ( int i = 1; i <= n - 1; i ++ )
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    dfs(1, 0);
    printf("%d\n", max(dp[1], g[1] + c[1]));
    return 0;   
}

f[i]为以i为根时，深度的最大和
f[v] = f[u] - size[v] * 2 + n由于从u转移到v，v的所有子节点深度都减少了1就有-size[v]，然后u的所有子结点深度加了1那么就有+n-size[u]。
只要先dfs一次将size和dep计算出，再dfs求dp转移就好了。
f[e[i].to] = f[u] - size[e[i].to] * 2 + n;

#include <bits/stdc++.h>

using namespace std;

struct node 
{
    int to, next;
} e[1000010<<1];
int head[1000010<<1],tot;

void add(int u, int v)
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

long long n, size[1000010], dep[1000010];
long long f[1000010];

void dfs(int u, int fa)
{
    size[u] = 1;
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        if (e[i].to != fa)
        {
            dfs(e[i].to, u);
            size[u] += size[e[i].to];
        }
    }
}

void get_ans(int u, int fa)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        if (e[i].to != fa)
        {
            f[e[i].to] = f[u] - size[e[i].to] * 2 + n;
            get_ans(e[i].to, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    int u, v;    
    for (int i = 1; i <= n - 1; i ++)
    {
        scanf("%d %d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i ++) f[1] += dep[i];
    get_ans(1,1);
    long long int ans = -1;
    int id;
    for (int i = 1; i <= n; i ++) 
    {
        if (f[i] > ans)
        {
            ans = f[i];
            id = i;
        }
    }
    printf("%d\n", id);
    return 0;
}

转移方程：f[v] = f[u] + sum -size[v] * 2;
d[u] += (d[v] + size[v]);计算有深度的点权乘积和

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;

typedef long long ll;

struct node 
{
    int to, next;
} e[maxn<<1];
int tot, head[maxn<<1];
ll n, val[maxn], sum;
ll d[maxn], size[maxn];
ll f[maxn];

void add(int u, int v)
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

void dfs(int u, int fa)
{
    size[u] = val[u];
    for (int i = head[u]; i; i = e[i].next )
    {
        int v = e[i].to;
        if (v != fa)
        {
            dfs(v, u);
            size[u] += size[v];
            d[u] += (d[v] + size[v]);
        }
    }
}

void get_ans(int u, int fa)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v != fa)
        { 
            f[v] = f[u] + sum -size[v] * 2;
            get_ans(v, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++) 
    {
        scanf("%lld", &val[i]);
        sum += val[i];
    }
    int x, y;
    for (int i  = 1; i <= n - 1; i ++)
    {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1,0);
    // printf("f1 = %lld\n", f[1]); 
    f[1] = d[1];
    get_ans(1,0);
    ll ans = -1;
    for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 200010;
const ll INF = 1e55;


struct node 
{
    ll to, next, w;
} e[maxn<<1];

int tot, head[maxn<<1];
ll n, val[maxn], sum;
ll d[maxn], size[maxn];
ll f[maxn];

void add(ll u, ll v, ll w)
{
    e[++tot] = node{v, head[u], w};
    head[u] = tot;
}

void dfs(int u, int fa)
{
    size[u] = val[u];
    for (int i = head[u]; i; i = e[i].next )
    {
        ll v = e[i].to;
        if (v != fa)
        {
            dfs(v, u);
            size[u] += size[v];
            d[u] += (d[v] + size[v] * e[i].w);
        }
    }
}

void get_ans(int u, int fa)
{
    if (u == 1) f[u] = d[u];
    for (int i = head[u]; i; i = e[i].next)
    {
        ll v = e[i].to;
        if (v != fa)
        { 
            f[v] = f[u] + (sum -size[v]) * e[i].w - size[v] * e[i].w;
            get_ans(v, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    sum = 0;
    for (int i = 1; i <= n; i ++) 
    {
        scanf("%lld", &val[i]);
        sum += val[i];
    }
    ll x, y, z;
    for (int i  = 1; i <= n - 1; i ++)
    {
        scanf("%lld %lld %lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    dfs(1,1);
    // printf("f1 = %lld\n", f[1]); 
    f[1] = d[1];
    get_ans(1,1);
    ll ans = INF;
    for (int i = 1; i <= n; i ++) ans = min(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}