本文共 865 字,大约阅读时间需要 2 分钟。
1、
2、题目大意;
有n个点,已知他们之间的关系,连接是双向的,求删除哪个点可以使得剩下的各个部分的点的个数最少
用一个cnt[]数组记录下每个点有多少个子节点
那么我们要求的删除根节点u后剩余部分的最大数就是要么是u的子树中的最大值,要么是除去以u为根的树外的剩余结点数dp[u]=max(max(cnt[v]),n-cnt[u]);
3、AC代码:
#include#include #include using namespace std;#define N 100005#define INF 50010int v[N],tot,next[N],head[N];int cnt[N];int dp[N];int ans,res,n;void add_edge(int a,int b){ v[tot]=b; next[tot]=head[a]; head[a]=tot++;}void dfs(int u,int fa){ cnt[u]=1; for(int i=head[u]; i!=-1; i=next[i]) { int vv=v[i]; if(vv!=fa) { dfs(vv,u); cnt[u]+=cnt[vv];//计算出以u为根的子树的结点个数 ans=max(ans,cnt[vv]);//计算出以子节点为根的最大结点数,这也是去掉父节点u后,下边各部分的最大值 } } dp[u]=max(ans,n-cnt[u]); res=min(res,dp[u]);}int main(){ int a,b; scanf("%d",&n); tot=0; memset(head,-1,sizeof(head)); for(int i=1; i
转载地址:http://mrddi.baihongyu.com/