Eezie and Pie

登录—专业IT笔试面试备考平台_牛客网

题目大意：有1个n个点的树，1为根，每个点有一个点权di，代表从这个点开始向根的方向di个点的计数+1，求每个点的最终计数

思路：简化版的树上差分题，因为方向固定是从树叶向树根，所以只要dfs遍历所有点，用o[cnt]数组模拟栈，记录当前遍历的深度，每个点的num[i]+1，如果点权大于等于cnt，就什么也不做，否则找到该点能向上回溯的最远的点，该点

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, m;
int a[N], head[N], cnt=0, o[N], num[N], cnt2 = 0;
bool vis[N];
struct Edge
{
	int u, v, next;
}edge[N*2];//图很大，要用链式前向星存图
void addedge(int u, int v)
{
	edge[++cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void dfs(int u)
{
	o[++cnt2] = u;//记录每层深度对应的点的编号
	vis[u] = 1;
	for (int i = head[u]; i; i = edge[i].next)
	{
		int v = edge[i].v;
		if(!vis[v])
			dfs(v);//先向下遍历到头
	}
	if (a[u] >= cnt2)
	{
		num[u]++;//点权大于等于当前的深度，只将当前点+1即可
	}
	else
	{
		num[u]++;
		int lc = cnt2 - a[u];
		num[o[lc - 1]]--;//当前点+1，向上a[u]个点的父结点-1
	}
	cnt2--;//回溯，层数减
}
void add(int u, int faa)
{//将差分数组变成答案
	for (int i = head[u]; i; i = edge[i].next)
	{
		int v = edge[i].v;
		if (v == faa)
			continue;
		add(v, u);
		num[u] += num[v];
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		addedge(x, y);
		addedge(y, x);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	dfs(1);
	add(1, 0);
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", num[i]);
	}
	return 0;
}

的父结点的num-1