讨论 / 发代码求rp
fshp97 2013-11-04 17:52:43
点我顶贴 收藏 删除
#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

int n;

int e[200010],h[100010],nex[200010];

int f[100010][2],del[100010];

void run1(int fa,int x);

void run2(int fa,int x);

int max(int a,int b){return (a>b)?a:b;}

void init(void)

{

int i,x,y,k=0,m;

memset(e,0,sizeof(e));

memset(h,0,sizeof(h));

memset(nex,0,sizeof(nex));

memset(f,0,sizeof(f));

scanf("%d%d",&n,&m);

for(i=1;i<=n-1;i++)

{

scanf("%d%d",&x,&y);

k++;

e[k]=y;

nex[k]=h[x];

h[x]=k;

k++;

e[k]=x;

nex[k]=h[y];

h[y]=k;

}

if(m==1)

run1(1,1);

else

run2(1,1);

printf("%d",max(f[1][0],f[1][1]));

return;

}

void run2(int fa,int x)

{

int i=h[x];

if(e[i]==fa)

i=nex[i];

if(!i)

{

f[x][0]=0;

f[x][1]=1;

return;

}

f[x][1]=1;

while(i!=0)

{

if(e[i]!=fa)

{

run2(x,e[i]);

f[x][0]+=f[e[i]][0];

del[x]=max(del[x],f[e[i]][1]-f[e[i]][0]);

f[x][1]+=f[e[i]][0]-del[e[i]];

}

i=nex[i];

}

f[x][0]+=del[x];

return;

}

void run1(int fa,int x)

{

int i=h[x];

if(e[i]==fa)

i=nex[i];

if(!i)

{

f[x][0]=0;

f[x][1]=1;

return;

}

f[x][1]=1;

while(i!=0)

{

if(e[i]!=fa)

{

run1(x,e[i]);

f[x][0]+=max(f[e[i]][1],f[e[i]][0]);

f[x][1]+=f[e[i]][0];

}

i=nex[i];

}

return;

}

int main(void)

{

init();

return 0;

}

测试点1 Accepted / 24ms / 5008kB

测试点2 Accepted / 23ms / 5008kB

测试点3 Accepted / 14ms / 5008kB

测试点4 Accepted / 112ms / 7776kB

测试点5 Accepted / 149ms / 5008kB

测试点6 Accepted / 15ms / 5008kB

测试点7 Accepted / 20ms / 5008kB

测试点8 Accepted / 19ms / 5008kB

测试点9 Accepted / 148ms / 8776kB

测试点10 Accepted / 98ms / 5008kB

#1 NEW WORLD@2013-11-04 20:46:40
回复 删除
c++
查看更多回复
提交回复