BZOJ-1907: 树的路径覆盖

Description

多组询问t<=10,n<=10^4

树形DP。
f[x]表示x的字数都已被覆盖，x为其中一个链的端点的情况。g[x]表示不为端点的情况。
对于一个x，他的儿子y中，选择0,1,2个为链的端点进行转移。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,head[10100],to[20100],nxt[20100],cnt;
inline void add(int x,int y)
{to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}

int f[10100],g[10100];
void dfs(int x,int pre)
{
    int sum=0,mi1=inf,mi2=inf;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        dfs(to[i],x); sum+=g[to[i]];
        if(f[to[i]]-g[to[i]]<=mi1) mi2=mi1,mi1=f[to[i]]-g[to[i]];
        else if(f[to[i]]-g[to[i]]<mi2) mi2=f[to[i]]-g[to[i]];
    }
    g[x]=min(sum+1,min(sum+mi1,sum+mi1+mi2-1));
    f[x]=min(sum+1,sum+mi1);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof head); cnt=0;
        scanf("%d",&n); int i,x,y;
        for(i=1;i!=n;++i)
        {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        dfs(1,0);
        printf("%d\n",min(g[1],f[1]));
    }
    return 0;
}