洛谷P1600 [NOIP2016 提高组] 天天爱跑步

前言

AC第一道紫题！！！

（梳理一下思路 顺便纪念一下）

题面

样例输入 #1

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

样例输出 #1

2 0 0 1 1 1

思路过程

1. 因为此题中提到了关于路线的事情，因此初步判定要写LCA,故首先倍增求LCA。
2. 尝试模拟此过程。 在最理想的情况下（即树非常匀称），模拟一个玩家的跑步过程时间复杂度为O(log(n))，共m个玩家，因此为O(m·log(n))。
3. 但是，数据中提示了树会退化成链，因此最坏时间复杂度为O(m·n)，不可通过。
4. 发现无法优化每个模拟跑步的过程。
5. 转换问题。 如果每次不枚举运动员i,而是枚举观察员i，查找能为此观察员做贡献的节点，就成为了DFS整棵树的过程，时间复杂度O(n) 。

如何统计一名选手对一个位于s->t的路线上的观察员P的贡献？

1. 分情况考虑。若P在s->LCA的路上，很容易可以得到结论: 若dep[s]=w[p]+dep[p],则运动员到达p会需要dep[p]-dep[s]=w[p]的时间,会对观察员P做一个贡献。
2. 否则，若P在LCA->t的路上，定义dis[s,t] 为s到t的路径长度（即dis[s,LCA]+dis[LCA,t]），若运动员从s出发并且可以被P看到，则有dis[s,t]-dep[t]+dep[p]=w[p]。
3. 总结：上行过程中，满足第7点的条件的点会对P作出贡献；下行过程中，满足第8点的条件的点会对P做出贡献，但是能对P做出贡献的点的起点或者终点一定在以P为根的子树上。因此，回溯时候处理信息。
4. 然后对于一个点我们可以记录下当前点出发的节点数，每次深搜到该点就对计数数组累加。
5. 同时我们扫描当前节点作为哪些子节点的 LCA 出现过，将这些子节点的贡献减掉就可以达到树上差分的效果了。
6. 遍历两次树(第一次s->LCA,第二次LCA->s )，即可获得以上信息。

对于一个s和t的LCA点P,如何防止重复计算贡献？

可以观察到，如果某个节点P是s和t的LCA点，那么该节点的贡献会被累加两次。

消除方法:

1. 暴力删除，在程序最后枚举m条路径的LCA并判断是否给了贡献，有的话就减贡献。
2. 修改遍历树的方式。 第二次遍历树的时候先对以P为LCA的路径上的重点信息忽略，然后再统计贡献。

代码实现：

Ⅰ.建树&倍增LCA

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;

//I.建树&倍增LCA 
int fa[N][30];//fa[i][j]表示第i个节点向上走2^i步到达的点 
int dep[N];//每个节点的深度 
int w[N];//w[i] 第i个节点出现观察员的时间
vector<int> v[N];//邻接表
int n,m;//如题 

void dfs(int u,int f){
	//递归建树
	fa[u][0]=f;
	dep[u]=dep[f]+1;
	for(int i=1;(1<<i)<=dep[u];i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];//倍增 
	} 
	for(int i=0;i<v[u].size();i++){
		int to=v[u][i];
		if(to==f) continue;
		dfs(to,u);
	}
} 

int lowbit(int x){
	return x&-x;
}

int getLCA(int x,int y){
    //倍增查询x和y的LCA点 
	if(dep[x]<dep[y])swap(x,y);
	for(int i=dep[x]-dep[y];i;i-=lowbit(i)){
		x=fa[x][int(log2(lowbit(i)))];
	}
	if(x==y)return x;
	for(int i=log2(dep[x]);i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}

Ⅱ. 统计贡献&解决问题(重点!)

int bup[2*N];//上行阶段的贡献统计 
int bdn[2*N];//下行阶段的贡献统计 
//上述两个桶完成树上差分操作 
vector<int>vend[N];//每个节点作为终点的路径集合
vector<int>vlca[N];//每个节点作为LCA点对应的集合
//注意: 上述两个邻接表并非传统意义上的邻接表
//而是（以vend[i]为例)存储的以i为终点的路径编号 
int st[N];//每个节点作为起点的路径条数
int dis[N];//m条路径的长度
int s[N],t[N];//每条路径的起点终点
int ans[N];//最后的答案，每个观察员看到的人数
 
void dfs2(int x){
	int tup=bup[w[x]+dep[x]];
	int tdn=bdn[w[x]-dep[x]+N];
	//递归前记录数据,只有在该子树递归过程中新形成的数据才是有效的 
	//+N是防止w[x]<dep[x]RE，因此bdn也要开两倍空间
	for(int i=0;i<v[x].size();i++){
		//递归子树 
		int to=v[x][i];
		if(to==fa[x][0])continue;
		dfs2(to); 
	}
	bup[dep[x]]+=st[x];
	//上行过程中当前点（为其他点）做出贡献 
	for(int i=0;i<vend[x].size();i++){
		int to=vend[x][i];
		bdn[dis[to]-dep[t[to]]+N]++;
		//下行过程中 当前节点为其他点做出贡献
		//dis[s,t]-dep[t]=w[p]-dep[p],则有贡献 
	} 
	ans[x]+=bup[w[x]+dep[x]]-tup;//只有建树后的差距才有效
	ans[x]+=bdn[w[x]-dep[x]+N]-tdn;
	
	//若该点正好为s->t的LCA点，则s-t路径对其上面的点无贡献，删除其贡献
	for(int i=0;i<vlca[x].size();i++){
		int to=vlca[x][i];
		bup[dep[s[to]]]--;
		bdn[dis[to]-dep[t[to]]+N]--;
	} 
} 

Ⅲ.主函数

int main(){
	cin>>n>>m;
	int x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);//无根树转有根树,建树 
	for(int i=1;i<=n;i++){
		cin>>w[i];
	} 
	for(int i=1;i<=m;i++){
		cin>>s[i]>>t[i];
		int lca=getLCA(s[i],t[i]);
		dis[i]=dep[s[i]]+dep[t[i]]-2*dep[lca];//计算路径长度
		st[s[i]]++;
		vend[t[i]].push_back(i);
		vlca[lca].push_back(i);
		if(dep[lca]+w[lca]==dep[s[i]]){
			ans[lca]--;
			//如果位于lca点的观察员恰好能看见运动员
			//这样会重复算两边贡献(s->lca一次，lca->t一次)
			//因此，提前-1
		}
	}
	dfs2(1);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}

啊啊啊啊啊啊啊啊啊啊啊啊啊入谷快一年了 AC的第一道紫题！！！