树形DP

树形DP

九月 01, 2021

树形DP

定义：在树上进行DP操作（没了）

树的直径

dfs

两次dfs，第一次从任意一个点出发，跑到最远的一个点，然后第二次从最远的那个点开始跑，找到最远的一个点，两个点之间的路径就是树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+10;
struct edge{
    int to,nxt,val;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].val=w;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m,dis[N];
bool vis[N];
inline void dfs(int u){
    // cout<<u<<" "<<dis[u]<<endl;
    vis[u]=true;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(vis[v]) continue;
        dis[v]=dis[u]+w;
        dfs(v);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v,w;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1);
    int pos=0,ans=0;
    for(int i=1;i<=n;i++){
        if(dis[i]>ans) ans=dis[i],pos=i;
        dis[i]=0;
    }
    memset(vis,0,sizeof(vis));
    dfs(pos);
    ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
    cout<<ans<<endl;
    return 0;
}

树形dp

我们设$f_x$表示$x$当前的最大值

然后就结束了

直接由其下面的几个子树的最大值和次大值相加就行了

最后记录答案就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int N=1e5+10;
struct edge{
    int to,val,nxt;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].val=w;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int ans=0;
inline int dp(int u,int f){
    int tag=0;
    int d1=0,d2=0;///存当前节点各个子树的较大值和次大值
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(v==f) continue;
        int d=dp(v,u)+w;
        tag=max(tag,d);
        if(d>d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }
    ans=max(ans,d1+d2);
    return tag;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1,u,v,w;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dp(1,0);
    cout<<ans;
}

树的中心

题目描述：请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。
典型的换根DP了，我们发现每一个点的转移的代价是可以由前一个点继承来的，所以可以直接进行树上DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=1e5+5;

struct edge{
    int to,nxt,val;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].val=w;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
template <typename T>
void read(T &x){
    x=0; char c=getchar(); int f=0;
    for(; !isdigit(c); c=getchar()) f |= c=='-';
    for(; isdigit(c); c=getchar()) x = (x<<3)+(x<<1)+(c^48);
    if(f) x = -x;
}
template <typename T>
void write(T x){
    if(x<0) putchar('-'), x = -x;
    static short st[30],tp;
    do st[++tp] = x%10, x/=10; while(x);
    while(tp) putchar(st[tp--] | 48);
    putchar('\n');
}

int p1[N];
int n,m;
int up[N];
pair<int,int> down[N];

inline int dfs_down(int u,int f){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(v==f) continue;
        int d=dfs_down(v,u)+w;
        if(down[u].first<d){
            p1[u]=v;
            down[u].second=down[u].first;
            down[u].first=d;
        }
        else if(down[u].second<d) down[u].second=d;
    }
    return down[u].first;
}

inline void dfs_up(int u,int f){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(v==f) continue;

        if(p1[u]==v) up[v]=max(down[u].second,up[u])+w;
        else up[v]=max(up[u],down[u].first)+w;
        
        dfs_up(v,u);
    }
}
int main(){
    read(n);
    for(int i=1,u,v,w;i<n;i++){
        read(u),read(v),read(w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs_down(1,-1);
    dfs_up(1,-1);
    int ans=2e9;
    for(int i=1;i<=n;i++) ans=min(ans,max(down[i].first,up[i]));
    write(ans);
    return 0;
}