树形DP例1

题面描述

给定一棵n个点的无权树，问树中每个节点的深度和每个子树的大小? （以1号点为根节且深度为0）

输入格式

第1行：n。

第2~n行：每行两个数x,y，表示x,y之间有一条边。

输出格式

n行，每行输出格式为：#节点编号 deep：深度 count：子树节点数（详见样例）

样例

这应该不算是树形DP，因为我感觉这就是个dfs遍历，在回溯时记录即可

代码

#include<bits/stdc++.h>
using namespace std;
int si[1001000],de[1001000],head[1001000],ver[1001000],ne[1001000],tot=0;
void add(int x,int y)
{
	ver[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
 } 
void dfs(int x,int y,int z)
{
	si[x]=1;
	de[x]=z;
	for(int i=head[x];i;i=ne[i])
	{
		if(ver[i]==y)
		continue;
		dfs(ver[i],x,z+1);
		si[x]+=si[ver[i]];
	}
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0,0);
	for(int i=1;i<=n;i++)
	{
		printf("#%d deep:%d count:%d\n",i,de[i],si[i]);
	}
	return 0;
}