[Elite 2010 January Competition Gold 【telephone】]树形dp

【题目链接】http://ace.delos.com/ioigate
另外八中OJ的1785也是。不过八中的可能pascal会爆栈。。。
【算法分析】
首先建议看英文，八中的翻译有点歧义。
这个一颗无根树，于是我们可以选一个非叶结点出来当根，那么就可以搞了。
然后我们注意到，如果两个叶子搞在一块的话，那么必然是连到它们的LCA那里去搞了。
如果是这样的话，如果是从某一个结点搞上它父亲那里的话，无论是哪个都是一样的。
因为都是占用父亲的链。
而且显然是越早解决越好。
于是我们直接用一个rest数组记录剩下多少个需要用连向父亲这条边来解决。
然后，都算不上dp了，就是统计算一下就可以了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:telephone
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int x,y,next;}g[N*2];
int n,k,e,root,ans;
int ls[N],du[N],rest[N];

void add(int x,int y){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void init(){
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
e=0;
scanf("%d%d",&n,&k);
for (int x,y,i=1;i scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
du[x]++; du[y]++;
}
}

void dfs(int p,int fa){
if (du[p]==1){
rest[p]=1;
return;
}
for (int t=ls[p];t;t=g[t].next)
if (g[t].y!=fa){
dfs(g[t].y,p);
rest[p]+=rest[g[t].y];
}
if (rest[p]<=2*k && rest[p]%2){
ans+=rest[p]>>1;
rest[p]=1;
}
else{
if (rest[p]>2*k) ans+=k;
else ans+=rest[p]>>1;
rest[p]=0;
}
}

void solve(){
if (n<=2){
printf("%dn",n);
return;
}
for (int i=1;i<=n;i++)
if (du[i]>1){
root=i;
break;
}
memset(rest,0,sizeof(rest));
ans=0;
dfs(root,0);
}

int main(){
init();
solve();
cout << ans << endl;
return 0;
}