Rockdu's Blog

小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含  个结点和  条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从  到  的连续正整数。

现在有  个玩家，第  个玩家的起点为 ，终点为 。每天打卡任务开始时，所有玩家在第  秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点  的观察员会选择在第  秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第  秒也正好到达了结点 。小C想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点  作为终点的玩家：若他在第  秒前到达终点，则在结点  的观察员不能观察到该玩家；若他正好在第  秒到达终点，则在结点  的观察员可以观察到这个玩家。

输入格式

从标准输入读入数据。

第一行有两个整数  和 。其中  代表树的结点数量，同时也是观察员的数量， 代表玩家的数量。

接下来  行每行两个整数  和 ，表示结点  到结点  有一条边。

接下来一行  个整数，其中第  个整数为 ，表示结点  出现观察员的时间。

接下来  行，每行两个整数  和 ，表示一个玩家的起点和终点。

对于所有的数据，保证 ，。

输出格式

输出到标准输出。

输出  行  个整数，第  个整数表示结点  的观察员可以观察到多少人。

样例一

input

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

output

2 0 0 1 1 1

explanation

对于  号点，，故只有起点为  号点的玩家才会被观察到，所以玩家  和玩家  被观察到，共  人被观察到。

对于  号点，没有玩家在第  秒时在此结点，共  人被观察到。

对于  号点，没有玩家在第  秒时在此结点，共  人被观察到。

对于  号点，玩家  被观察到，共  人被观察到。

对于  号点，玩家  被观察到，共  人被观察到。

对于  号点，玩家  被观察到，共  人被观察到。

样例二

input

5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5

output

1 2 1 0 1

限制与约定

每个测试点的数据规模及特点如下表所示。提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。

测试点编号			约定
1			所有人的起点等于自己的终点，即
2
3
4
5			无
6			树退化成一条链，其中  与  有边， 与  有边，， 与  有边
7
8
9			所有的
10
11
12
13			所有的
14
15
16
17			无
18
19
20

一年前一点思路也没有的题，时隔一年，总算能想能做了。

首先发现每一条路径其实是一个等差数列，可以简化问题，我们把这个等差数列从u,v的lca拆成两段(lca既可以属于左边也可以属于右边)。

那么现在我们的每一条路径都是从点u到自己祖先的了。

这时这道题突然就有了时空危机的感觉：或许可以一边dfs一边维护一个桶？

我们先来看看我们处理出了哪些东西：

假设当前dfs到的点为x。

对于一条红色路径来说，要被看到需要满足：depth[u] = depth[x] + w[x]

对于一条绿色路径来说，要被看到需要满足：w[x] - depth[x] = dis[u][v] - depth[v]

那么我们把每一条路径拆成4个操作：在u加入depth[u] = depth[x] + w[x]、在v加入dis[u][v] - depth[v]、在lca删除dis[u][v] - depth[v]、在lca的父亲删除depth[u] = depth[x] + w[x]。每一个点开一个vector，表示从这个点退出dfs前要执行的操作。

对于每一个查询，只要在进入dfs的时候记下当前的红、绿路径对应的桶的数值bef[红/绿]，在退出dfs的时候对应的答案就是桶的答案[红/绿]-bef[红/绿]，这样就可以实时维护每一个点为子树的桶了。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 3e5 + 5;
struct edge {
	int v, next;
} e[maxn << 1];
struct OPR {
	int opr, id, x;
};
int head[maxn], cnt;
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
int tp[maxn], fa[maxn], son[maxn], siz[maxn], depth[maxn];
int n, m, u, v, w[maxn], ans[maxn], ton[2][maxn * 3];
vector<OPR > oprs[maxn];
void dfs1(int u, int p) {
	siz[u] = 1;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dfs1(v, u), siz[u] += siz[v];
		if(!son[u] || siz[v] > siz[son[u]])
			son[u] = v;
	}
}

void dfs2(int u, int p, int top) {
	depth[u] = depth[p] + 1;
	fa[u] = p, tp[u] = top;
	if(son[u]) dfs2(son[u], u, top);
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == son[u] || v == p) continue;
		dfs2(v, u, v);
	}
}

int LCA(int a, int b) {
	while(tp[a] != tp[b]) {
		if(depth[tp[a]] < depth[tp[b]]) swap(a, b);
		a = fa[tp[a]];
	}
	if(depth[a] < depth[b]) return a;
	return b;
}

void dfs(int u, int p) {
	int bef[2] = {ton[0][depth[u] + w[u]], ton[1][w[u] - depth[u] + n]};
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dfs(v, u);
	}
	for(register int i = oprs[u].size() - 1; i >= 0; --i) {
		ton[oprs[u][i].id][oprs[u][i].x] += oprs[u][i].opr;
		//cerr << u << " " << oprs[u][i].id << " " << oprs[u][i].x << " " << oprs[u][i].opr << endl;
	}
	ans[u] += ton[0][depth[u] + w[u]] - bef[0];
	ans[u] += ton[1][w[u] - depth[u] + n] - bef[1];
}

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	}
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	dfs1(1, 0), dfs2(1, 0, 1);
	int lca, ds;
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		lca = LCA(u, v), ds = depth[u] + depth[v] - 2 * depth[lca];
		oprs[u].push_back((OPR) {1, 0, depth[u]});
		oprs[v].push_back((OPR) {1, 1, ds - depth[v] + n});
		oprs[lca].push_back((OPR) {-1, 1, ds - depth[v] + n});
		oprs[fa[lca]].push_back((OPR) {-1, 0, depth[u]});
	}
	dfs(1, 0);
	for(register int i = 1; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
	return 0;
}