题意:
一棵树上有至多20000个点...现在问拆掉一个点..可以使得最多的两两不可达..输出最大的两两部可达..
题解:
只需统计以某点为根的子树节点数量..就可以推出每个点的答案了..找到最大的就是..而统计每个点做子树根节点数量..就是一个基本的树形DP...
Program:
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define MAXN 20005 using namespace std; struct node { int v,next; }edge[MAXN<<1]; int Ne,_next[MAXN],sum[MAXN],ans; void addedge(int u,int v) { edge[++Ne].next=_next[u],_next[u]=Ne; edge[Ne].v=v; } void dfs(int father,int u,int N) { int k,v,m,temp; for (k=_next[u];k;k=edge[k].next) { v=edge[k].v; if (v==father) continue; dfs(u,v,N); sum[u]+=sum[v]; } m=sum[u]*(N-1-sum[u]),temp=0; for (k=_next[u];k;k=edge[k].next) { v=edge[k].v; if (v==father) continue; temp+=sum[v]*(sum[u]-sum[v]); } m+=temp/2; ans=max(ans,m); sum[u]++; } int main() { int C,cases,N,u,v,i; scanf("%d",&C); for (cases=1;cases<=C;cases++) { scanf("%d",&N); Ne=0,memset(_next,0,sizeof(_next)); for (i=1;i<N;i++) { scanf("%d%d",&u,&v); addedge(u,v),addedge(v,u); } ans=0; memset(sum,0,sizeof(sum)); dfs(0,1,N); printf("Case #%d: %d\n",cases,ans); } return 0; }