时间戳

首页 > 技术文章 > 天天爱跑步 题解

天天爱跑步 题解

yangchengcheng 2021-06-14 18:05 原文

天天爱跑步 题解

原文链接：https://www.cnblogs.com/lfyzoi/p/10221884.html (如果真的要看，建议去原文，有图)

LCA + 桶 + 树上差分

Step1

先对每一个运动员的路径求LCA， 枚举每个观察员，看有哪些节点在第\(w_i\)秒会为这个观察员做贡献。

int f[maxn][30], dep[maxn];
void dfs(int u, int fa)
{
		for(int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].v;
			if(v != fa) { f[v][0] = u; dep[v] = dep[u] + 1; dfs(v, u);}
		}
}
void bz() 
{
	for(int j = 1; j <= 20; j++)
	{
		for(int i = 1; i <= n;i++) f[i][j] = f[f[i][j-1]][j-1];
	}	
}
int lca(int x, int y)
{
	if(dep[x] < dep[y]) swap(x,y);
	while(dep[x] > dep[y])
	{
		int z = log2(dep[x]-dep[y]);
	    x = f[x][z];
	}
	if(x == y)  return x; 
	for(int j = log2(dep[x]); j >= 0; j--)
	{
		if(f[x][j] != f[y][j]) { x = f[x][j]; y = f[y][j];}
	}
	return f[x][0];
}

Step2

对于节点P，该如何判断这名选手会不会为P做贡献呢？

分情况讨论：

  1. 如果P点是在这名选手从起点到LCA的路上，

    有一个结论， 当\(deep[s_i] = w[P] + deep[P]\)时，这名运动员可以为P点做贡献。

    （\(deep[s_i] = deep[P] + dis[s_i][P]\) ， 如果\(w[p] == dis[s_i][P]\), 即\(deep[s_i] = w[P] + deep[P]\)，

    这名运动员可以为P点做贡献）。

  2. 如果P点是在这名选手从LCA到终点的路上，

    当\(dis[s_i][t_i] - w[P] = deep[t_i] - deep[P]\)， 即\(dis[s_i][t_i] - deep[t_i] = w[P] - deep[P]\)， 时,

​ 这名运动员可以为P点做贡献。

总结：上行过程中，满足条件的起点可以做贡献，下行过程中，满足条件的终点可以做贡献，但无论是哪一种情形，能对 P 做贡献的起点或终点一定都在以P为根的子树上（一定会经过P点），这使得可以在DFS回溯的过程中处理以任意节点为根的子树。

Step3

开始糊了

递归以P为根的子树时，可以统计子树中所有的起点与终点对它的贡献。

子树中有的起点和终点对P产生了贡献，有些不对P产生贡献，但对其他结点产生了贡献。

所以我们不能枚举每个点，找子树中哪些点对其产生贡献，这样复杂度就上去了。

而是对于树上的任何一个起点和终点，把其产生的贡献放在桶里面，回溯到子树根的时候再到桶里面查

询结果。

对于一个点P来说，以P为根递归整颗子树过程中在桶内产生的差值才是有效的。

还有一种情况，对于以P为根的内部路径（不经过P）的起点和终点产生的贡献是不应该属于P的。

所以dfs过程中，在统计当前结点作为起点和终点所产生的贡献后，继而计算出当前结作为“根”上的差值后，在回溯过程中，一定要减去以当前结点为LCA的起点、终点在桶里产生的贡献，这部分贡献在离开这个子树后就没有意义了。

如果路径起点或终点刚好为LCA且LCA处是可观察到运动员的，那么我们在上行统计过程中和下行统计过程中都会对该LCA产生贡献，这样就重复计数一次！

好在这种情况很容易发现，我们提前预测到，对相应的结点进行ans[x]--即可。

此外，在使用第二个桶时，下标是w[x]-deep[x]会成为负数，所以使用第二个桶时，下标统一+SIZE，向右平移一段区间，防止下溢。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define orz cout << "AK IOI" <<"\n"

using namespace std;
const int maxn = 300000;

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch<= '9') { x = x * 10 + ch - '0'; ch = getchar();}
	return x*f;
}
int n, m, w[maxn], dis[maxn], cnt[maxn], ans[maxn];
struct node{
	int u, v, nxt;
}e[maxn << 1], e1[maxn << 1], e2[maxn << 1];

int js, head[maxn];
void add(int u, int v)
{
	e[++js] = (node){u, v, head[u]};
	head[u] = js;
}

int f[maxn][30], dep[maxn];
void dfs(int u, int fa)
{
		for(int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].v;
			if(v != fa) { f[v][0] = u; dep[v] = dep[u] + 1; dfs(v, u);}
		}
}
void bz() 
{
	for(int j = 1; j <= 20; j++)
	{
		for(int i = 1; i <= n;i++) f[i][j] = f[f[i][j-1]][j-1];
	}	
}
int lca(int x, int y)
{
	if(dep[x] < dep[y]) swap(x,y);
	while(dep[x] > dep[y])
	{
		int z = log2(dep[x]-dep[y]);
	    x = f[x][z];
	}
	if(x == y)  return x; 
	for(int j = log2(dep[x]); j >= 0; j--)
	{
		if(f[x][j] != f[y][j]) { x = f[x][j]; y = f[y][j];}
	}
	return f[x][0];
}
//--------------------------------------------------------------------------------------------------
struct peo{
	int s, t;
}a[maxn];
int js1, js2, head1[maxn], head2[maxn];
void add1(int u, int v)
{
	e1[++js1] = (node){u, v, head1[u]};
	head1[u] = js1;
}
void add2(int u, int v)
{
	e2[++js2] = (node){u, v, head2[u]};
	head2[u] = js2;
}
int b1[maxn << 1], b2[maxn << 1]; 
void dfs2(int x)
{
	int t1 = b1[w[x] + dep[x]], t2 = b2[w[x] - dep[x] + maxn];//读桶取里的数值，t1是上行桶里的值，t2是下行桶的值
	for(int i = head[x]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if(v == f[x][0]) continue;
		dfs2(v);
	}
	b1[dep[x]] += cnt[x];//上行过程中，当前节点作为起点产生的贡献
	for(int i = head1[x]; i; i = e1[i].nxt)//下行过程中，当前节点作为终点产生的贡献
	{
		int v = e1[i].v;
		b2[dis[v] - dep[a[v].t] + maxn]++;
	} 
	ans[x] += b1[w[x] + dep[x]] - t1 + b2[w[x] - dep[x] + maxn] - t2;//计算上、下行桶内差值
	for(int i = head2[x]; i; i = e2[i].nxt)//清除 
	{
		int v = e2[i].v;
		b1[dep[a[v].s]]--;
		b2[dis[v] - dep[a[v].t] + maxn]--; 
	}
}
int main()
{
	n = read();  m = read();
	for(int i = 1; i < n; i++)
	{
		int x = read(), y = read();
		add(x, y), add(y, x);
	}
	dep[1] = 1; f[1][0] = 1; dfs(1, -1); bz();
	for(int i = 1; i <= n; i++) w[i] = read();
	for(int i = 1; i <= m; i++) 
	{
		a[i].s = read(), a[i].t = read();
		int LCA = lca(a[i].t, a[i].s);
		dis[i] = dep[a[i].s] + dep[a[i].t] - 2 * dep[LCA];
		cnt[a[i].s]++;                          //便于统计上行过程中该节点的贡献 
		add1(a[i].t, i), add2(LCA, i); //把第i条路径加到以t[i]为终点的路径集合中
		if(dep[LCA] + w[LCA] == dep[a[i].s]) ans[LCA]--; 
 	}
	dfs2(1);
	for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

推荐阅读