题目大意

原题目POJ-1655(戳这里)
给定T组数据,每组数据包含一棵树(树结点个数,两点连通),现去掉一个结点使得成为一片森林,求满足此时得到子树最大结点数最小的断开处结点p和最大结点数n。

举个栗子OwO


断掉结点1,得到的是2-6 4-5 3-7三棵子树,此时这三棵子树结点最大值为2,满足题意且为最优。

样例输入

1
7
2 6
1 2
1 4
4 5
3 7
3 1

样例输出

1 2

来自

POJ Monthly–2004.05.15 IOI 2003 sample task

思路

树形dp,每个结点用d[i] t[i] vis[i]维护,d[i]表示该结点能管理的结点个数(包含自己和以自己为根的子树),t[i]表示断开i结点时生成的最大子树大小,回溯时维护t[i]即可。
有关DFS的补充:

void dfs(int now){
    /*发现时间*/
    if(条件){}
    for(i in son[now]){
        if(条件){
            dfs(i);
            /*回溯*/
        }
    }
    /*离开时间*/
}

本题中更新t[i]就是在回溯时更新的
d[now]+=d[G[now][i]];
这样可以降低时间复杂度

代码:

/*O(N)算法*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#define N 20000+5
#define INF 2147483646
using namespace std;

int T,n,a,b,vis[N],d[N],t[N];
vector<int>G[N];
void addedge(int x,int y){G[x].push_back(y);G[y].push_back(x);}

void dfs(int now,int fa){
    if(G[now].size()==0) return;
    int max_t=-1;
    for(int i=0;i<G[now].size();i++)
        if(!vis[G[now][i]]){
            vis[G[now][i]]=1;
            dfs(G[now][i],now);
            d[now]+=d[G[now][i]];
            if(max_t<d[G[now][i]]) max_t=d[G[now][i]];
        }
    t[now]=max(max_t,n-d[now]);
}

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<=N;i++) d[i]=1;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<n;i++){
            cin>>a>>b;
            addedge(a,b);
        }
        vis[1]=1;
        dfs(1,0);
        int min_t=INF-1,node;
        for(int i=1;i<=n;i++){
            if(min_t>t[i]){min_t=t[i];node=i;}
        }
        cout<<node<<" "<<min_t<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.