FZOJ 2185 树的路径覆盖（YY+DFS）

//Accepted 2576 625ms GNU C++ 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5+100;

int head[N];
struct Edge
{
    int to;
    int next;
}es[N<<1];


int son[N];
int n;
int ans1,ans2;
void dfs(int rt,int pa)
{
    int cnt=0;
    bool first=1;
    for(int i=head[rt];~i;i=es[i].next)
    {
        int v=es[i].to;
        if(v==pa) continue;
        if(first)
            first=0;
        else
        {
            ans1++;
            cnt++;
        }
        dfs(v,rt);
    }
    ans2+=cnt/2+cnt%2; //剔除同一节点的分枝数
}

void ini()
{
    memset(head,-1,sizeof(head));
    memset(son,0,sizeof(son));
    ans1=ans2=0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ini();
        for(int v=1;v<n;v++)
        {
            int u;
            scanf("%d",&u);
            es[v].to=v;
            es[v].next=head[u];
            head[u]=v;
            es[v+n].to=u;
            es[v+n].next=head[v];
            head[v]=v+n;
            son[u]++;
            son[v]++;
        }
        for(int i=n-1;i>=0;i--)
            if(son[i]==1)
            {
                dfs(i,-1);
                ans1++;
                ans2++;
                break;
            }
        if(ans1)
            printf("%d %d\n",(ans1-1)/2+(ans1-1)%2+1,ans2);
        else
            printf("0 0\n");
    }
    return 0;
}