[树上倍增]Eezie and Pie 2022牛客多校第6场 B

题目描述

Eezie, a pie maniac, would like to have some pies with her friends on a hot summer day. However, the weather is so hot that she can't go outdoors and has to call for the delivery service.

The city Eezie lives in can be represented by NNN nodes connected by N−1N - 1N−1 edges, and the city center is node 111. In other words, the city is a rooted tree, root of which is node 111. There are NNN pie houses in the city, the iii-th on node iii. For some reason, a pie house on node iii can only deliver its pie to nodes on the simple path from node iii to node 111.

Eezie is a bit worried that a pie might lose its flavor during the deliver. After some careful calculation, she decided that a pie from the iii-th pie house can maintain its flavor if the distance it is delivered does not exceed its flavor-loss-distance did_idi​. The distance between two nodes on the tree is the number of edges on the simple path between them.

Now, Eezie wants to order some pies for all her friends who live on different nodes of the tree. Therefore, she wants you to calculate for each node how many pie houses can deliver their pie to the node without flavor loss.

输入描述:

The first line contains an integer N(1≤N≤2×106)N(1\le N \le 2\times 10^6)N(1≤N≤2×106), representing the number of nodes of the city Eezie lives in.

Each of the next N−1N - 1N−1 lines contains two integers u,v(1≤u,v≤N)u, v(1\le u,v \le N)u,v(1≤u,v≤N), representing an edge. It is guaranteed that the edges form a tree.

The last line contains NNN integers d1,d2,⋯ ,dN(0≤di≤N)d_1, d_2, \cdots, d_N(0\le d_i \le N)d1​,d2​,⋯,dN​(0≤di​≤N), representing the maximum travel distances for pies from pie houses.

输出描述:

Output NNN integers in a line, the iii-th integer representing the answer for node iii.

示例1

输入

10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2

输出

6 6 2 3 1 1 1 2 1 1

题意： 给出一棵树，树上每个点有一个点权di，表示从该点出发向根节点走能走的最大距离，询问每个点能被多少个点经过，距离即为经过的边数。

分析： 每个点最多被其子树中的所有点经过，但是子树中有些点可能因为di不够大而无法到达，这些点会对向上走不到的点产生-1的贡献，所以可以将每个点第一个不能走到的点标记一下，然后统计某点贡献时就是子树中点数减子树中标记数。在求某点向上第一个不能走到的点时可以通过树上倍增来求，类似求lca向上跳的过程，最终时间复杂度O(nlogn)。

具体代码如下： 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
vector<int> tr[2000005];
int d[2000005], dep[2000005], fa[2000005][21], num[2000005], ans[2000005];
 
void dfs(int now, int pre)
{
	dep[now] = dep[pre]+1;
	fa[now][0] = pre;
	for(int i = 1; i <= 20; i++)//超出范围的祖先都是0号结点 
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int i = 0; i < tr[now].size(); i++){
		int to = tr[now][i];
		if(to != pre)
			dfs(to, now);
	}
}
 
void dfs2(int now, int pre){
	for(int i = 0; i < tr[now].size(); i++){
		int to = tr[now][i];
		if(to == pre) continue;
		dfs2(to, now);
		num[now] += num[to];
		ans[now] += ans[to];
	}
	ans[now]++;
}
 
signed main()
{
	int n;
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
	for(int i = 1; i <= n; i++){
		scanf("%d", &d[i]);
		num[i] = ans[i] = 0;
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++){
		int t = min(dep[i]-1, d[i]);
		t = dep[i]-t;
		int x = i;
		for(int j = 20; j >= 0; j--)
			if(dep[fa[x][j]] >= t)
				x = fa[x][j];
		num[fa[x][0]]--;
	}
	dfs2(1, 0);
	for(int i = 1; i <= n; i++)
		printf("%d ", num[i]+ans[i]);
    return 0;
}