题目地址：FZU 2185 允许重复覆盖的值比较好求，，一条路径覆盖两个叶子节点，所以答案是（叶子结点数+1）/2。至于不允许重复覆盖的，我第一次想的是叶子节点数-1，因为先让第一条覆盖两个叶子结点，后面的每条覆盖一个，但是显然作为渣渣的我太native了。 很显然，当所有叶子节点都指向一个节点的时候肯定不是，这时候可以一条路径覆盖两个叶子节点。 正确思路是：对于每一个节点来说，看它有几个儿子，这时候可以用一条路径来覆盖它的两个儿子结点，这时候还可以发现，可以让其中一个儿子与祖父结点到父节点的路径延长一下，就可以顺便覆盖一个儿子，所以这时候的路径个数就是num/2。当然对于无祖父结点的点来说，仍然是(num+1)/2. 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=300000+10;int deg[110000], head[110000], cnt, ans1, ans2, vis[110000];struct node{int u, v, next;}edge[210000];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void init(){memset(deg,0,sizeof(deg));memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));cnt=ans1=ans2=0;}void dfs(int u){vis[u]=1;int i, num=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(vis[v]) continue ;dfs(v);num++;}if(u==0) num++;ans2+=num/2;}int main(){int t, n, i, x;scanf(“%d”,&t);while(t–){scanf(“%d”,&n);init();for(i=1;i<n;i++){scanf(“%d”,&x);add(x,i);add(i,x);deg[x]++;deg[i]++;}if(n==1){printf(“0 0\n”);continue ;}ans1=0;for(i=0;i<n;i++){if(deg[i]==1) ans1++;}dfs(0);printf(“%d %d\n”,(ans1+1)/2,ans2);}return 0;}
我们可以沿途用镜头记录彼此的笑脸，和属于我们的风景。
