poj 1655 樹形dp
題意相當於給你一棵樹 讓你求每個點的不同子樹上的節點個數吧 注意存邊的時候存雙向邊
#include
#include
#include
using namespace std;
struct node
{
int to,next;
}A[40010];
int tot,list[20010],mark[20010],n;
int add(int a,int b)
{
A[++tot].to = b;
A[tot].next = list[a];
list[a] = tot;
return 0;
}
int dp[20010],subtree[20010];
int max(int a,int b)
{
return a>b?a:b;
}
int dfs(int point)
{
mark[point]=1;
int b;
int k=list[point];
if(k==-1) {dp[point]=n-1;subtree[point]=0;return 0;}
for(;k!=-1;k = A[k].next)
{
b = A[k].to;
if(mark[b]) continue;
dfs(b);
subtree[point]+=subtree[b]+1;
dp[point]=max(dp[point],subtree[b]+1);
}
dp[point]=max(dp[point],n-subtree[point]-1);
return 0;
}
int main()
{
int i,j,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
tot=1;
memset(list,-1,sizeof(list));
memset(mark,0,sizeof(mark));
for(i=1;i
