树形DP 三道例题（板子）

1、树的最大独立集
（tree1.cpp）
对于一棵n个节点的无根树，给出n-1条边，选出尽量多的节点，使得任何两个节点均不相邻（称为最大独立集）。输出一个最大独立集的数量。
【输入格式】
第一行一个整数n，表示结点数。接下来n-1行，每行两个整数a，b，表示结点a和b有边。
【输出格式】
一个整数表示最大独立集的数量。
【输入样例】
8
1 2
3 1
7 3
5 4
6 5
8 6
3 4
【输出样例】
4

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 500005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N];
int to[N];
int nex[N];
int tot,n;
int fa[100050][25];
int gs[N];
int s[N];
int d[N];

inline void add(int x,int y){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void dfs(int u,int fat){
    for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=nex[i]){
        int dmf=to[i];
        if(dmf==fat)continue;
        fa[dmf][0]=u;
        dfs(dmf,u);
    }
    d[u]=max(s[u],gs[u]+1);
    s[fa[u][0]]+=d[u];
    gs[fa[u][1]]+=d[u];
}
int main(){
    freopen("tree1.in","r",stdin);
    freopen("tree1.out","w",stdout);
    n=read();
    for(int i=1;i<n;i++){
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    printf("%d",d[1]);
    return 0;

}

2、树的重心
（tree2.cpp）
对于一棵n个结点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。
【输入格式】
第一行一个整数n，表示结点数。接下来n-1行，每行两个整数a，b，表示结点a和b有边。
【输出格式】
一行，两个整数，第一整数为删除的结点编号，第二个整数为删除此结点后其最大子树的结点数量。
【输入样例】
11
3 4
1 2
3 1
5 3
5 10
4 7
11 6
4 8
5 9
3 6
【输出样例】
3 3

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 500005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N];
int to[N];
int nex[N];
int son[N];
bool vis[N];
int tot,n;
int size;
int ans;
inline void add(int x,int y){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void dfs(int cur){
    vis[cur]=1;
    son[cur]=0;
    int tmp=0;
    for(int i=head[cur];i;i=nex[i]){
        int dmf=to[i];
        if(!vis[dmf]){
            dfs(dmf);

            son[cur]+=son[dmf]+1;
            tmp=max(tmp,son[dmf]+1);
        }
    }
    tmp=max(tmp,n-son[cur]-1);
    if(tmp<size||tmp==size&&cur<ans){
        ans=cur;
        size=tmp;
    }
}
int main(){
    freopen("tree2.in","r",stdin);
    freopen("tree2.out","w",stdout);
    n=read();
    size=2147483640;
    for(int i=1;i<n;i++){
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1);
    printf("%d %d\n",ans,size);
    return 0;

}

3、树的最长路径
（tree3.cpp）
对于一棵n个结点的无根树，找到一条最长路径。换句话说，要找到两个点，使得它们的距离最远。
【输入格式】
第一行一个整数n，表示结点数。接下来n-1行，每行两个整数a，b，表示结点a和b有边。
【输出格式】
一行，一个整数，表示最长路径的长度，即边的数量。
【输入样例】
6
1 2
3 1
4 3
5 3
5 6
【输出样例】
4

树形DP 三道例题（板子）

全站热榜