[NOIP2016]D1T2天天爱跑步解题报告

发表于 | 阅读次数：

题目

妈耶~自己找去。。。

题解

妈耶，终于把NOIP2016的题都啃下来了（我觉得这个最难。。）

这题主要的突破点就在于怎么把一条链的特殊情况想清楚。

如果一条链的会做，在树上也就不会有什么大问题了。

接下来我们直接讲树上的做法（各位大佬这么牛逼，还用管链上的吗？ε=ε=ε=┏(゜ロ゜;)┛逃

我们把一个人的路程分为两部分：起点到$LCA$，$LCA$到终点。

那么，在第一部分$(S \sim LCA)$中在$x$位置上的观察员看到玩家的前提是$w[x]=dep[S]−dep[x]$。

在第二部分$(LCA \sim T)$看到玩家的前提是$w[x]=len−(dep[T]−dep[x])$，其中$len$为起点到终点的长度。

把两个式子化为和$x$有关，就是$w[x]+dep[x]=dep[S],w[x]−dep[x]=len−deep[T]$。

我们只要把两个式子做成桶，然后对于每个点在遍历到时先记录一下对应桶内的初始值，因为此时桶里的值对他是不可能有贡献的，真正有贡献的是遍历完他的子树后与之前的值的差值。遍历完他的子树后我们先把把这个点作为起点的玩家信息塞进一个桶里，再把以这个点作为终点的玩家信息塞到另一个桶里，然后再统计答案。注意，如果一个点是一条路径上的$LCA$，那么，他如果会被观察到答案会被记录两次，所以我们要提前减去这个值。在这之后，我们再将以这个点作为$LCA$的所有路径在桶里清除掉就好了。

放代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <iostream>
#define Re register int
#define MAX_N 300000
using namespace std;

struct Edge{
	int to,next;
}e[2*MAX_N],G1[2*MAX_N],G2[2*MAX_N];
int cnt,cnt1,cnt2,head[MAX_N],head1[MAX_N],head2[MAX_N],maxd;
int N,M,W[MAX_N],S[MAX_N],T[MAX_N],dep[MAX_N],ans[MAX_N];
int Sum[MAX_N],f[MAX_N][20],l[MAX_N],T1[2*MAX_N],T2[2*MAX_N];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v)
{
	e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v]}; head[v]=cnt;
}
inline void AddEdge1(int u,int v) {G1[++cnt1]=(Edge){v,head1[u]};head1[u]=cnt1;}
inline void AddEdge2(int u,int v) {G2[++cnt2]=(Edge){v,head2[u]};head2[u]=cnt2;}
void preLCA(int now,int fa)
{
	dep[now]=dep[fa]+1; f[now][0]=fa; maxd=max(maxd,dep[now]);
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) preLCA(e[i].to,now);
	return;
}
inline int LCA(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	for (Re i=19; i>=0; --i)
		if (dep[u]<=dep[f[v][i]]) v=f[v][i];
	for (Re i=19; i>=0; --i)
		if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return u==v?u:f[u][0];
}
void dfs(int now,int fa)
{
	int Last1=T1[W[now]+dep[now]],Last2=T2[W[now]-dep[now]+MAX_N];
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) dfs(e[i].to,now);
	T1[dep[now]]+=Sum[now];
	for (Re i=head2[now];i;i=G2[i].next)
		++T2[l[G2[i].to]-dep[T[G2[i].to]]+MAX_N];
	ans[now]+=T1[W[now]+dep[now]]-Last1+T2[W[now]-dep[now]+MAX_N]-Last2;
	for (Re i=head1[now];i;i=G1[i].next)
		--T1[dep[S[G1[i].to]]],--T2[l[G1[i].to]-dep[T[G1[i].to]]+MAX_N];
}
int main(int argc, char const *argv[])
{
	read(N),read(M);
	for (Re i=1,u,v; i<N; ++i)
		read(u),read(v),AddEdge(u,v);
	for (Re i=1; i<=N; ++i) read(W[i]);
	for (Re i=1; i<=M; ++i)
		read(S[i]),read(T[i]),++Sum[S[i]];
	preLCA(1,0);
	for (Re j=1; (1<<j)<=maxd; ++j)
		for (Re i=1; i<=N; ++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for (Re i=1; i<=M; ++i)
	{
		int k=LCA(S[i],T[i]);
		l[i]=dep[S[i]]+dep[T[i]]-2*dep[k];
		if (W[k]==dep[S[i]]-dep[k]) --ans[k];
		AddEdge1(k,i); AddEdge2(T[i],i);
	} dfs(1,0);
	for (Re i=1; i<=N; ++i) printf("%d ",ans[i]);
	printf("\n"); return 0;
}