简要题意

树上n个节点，给定路径，求每个点经过次数

题意分析

对于每两个点，有两种情况，第一种，他们的lca为本身，第二种，他们有公共祖先，又要求他们的点经过次数，暴力是不可能的，复杂度不对，所以可以想到树上差分再求前缀和，在差分的过程中自然也要求lca了。

还有要注意的就是对于开始的起点和结束的终点是要特判经过的，其他的起点不计入次数。

树上差分

树上差分主要用于求解一些树上的路径问题

它通过利用树的一些性质，用一个差分数组来实现对一条路径的操作，这涉及到路径的起，终点与lca。

一般情况下：一个点的真实权值为其所在子树内所有点的差分数组的值的和

树上差分一般不适用于询问和操作嵌套的题目，这时一般用树链剖分解决

LCA

倍增Tarjan树剖，自行百度

关于代码：

#include<bits/stdc++.h>

#define re register

#define ll long long

#define File(x) freopen(x".in","r",stdin);   freopen(x".out","w",stdout)

using namespace std;

inline int read()

{

	int k=1,sum=0;

	char c=getchar();

	for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1;

	for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-'0';

	return sum*k;

}

const int N=3e5+10;

struct Edge

{

	int to,nxt;

}edge[N*2];

int head[N],cnt;

inline void Add(int x,int y)

{

	edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;

}

int n;

int a[N];

queue<int> Q;

int dep[N];

int t;

int f[N][26];

int cf[N];

inline void bfs()

{

	Q.push(1);

	dep[1]=1;

	while(!Q.empty())

	{

		int x=Q.front();Q.pop();

		for(re int i=head[x];i;i=edge[i].nxt)

		{

			int y=edge[i].to;

			if(dep[y]) continue;

			dep[y]=dep[x]+1;

			f[y][0]=x;

			for(re int j=1;j<=t;++j) f[y][j]=f[f[y][j-1]][j-1];

			Q.push(y);

		}

	}

}

inline int LCA(int x,int y)

{

	if(dep[x]>dep[y]) swap(x,y);

	for(re int i=t;i>=0;--i) if(dep[f[y][i]]>=dep[x]) y=f[y][i];

	if(x==y) return x;

	for(re int i=t;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

	return f[x][0];

}

bool vis[N];

inline void dfs(int x)

{

	vis[x]=1;

	for(re int i=head[x];i;i=edge[i].nxt)

	{

		int y=edge[i].to;

		if(vis[y]) continue;

		dfs(y);

		cf[x]+=cf[y];

	}

}

int main()

{

	n=read();t=(log(n)/log(2))+1;

	for(re int i=1;i<=n;++i) a[i]=read();

	for(re int i=1;i<n;++i)

	{

		int x=read(),y=read();

		Add(x,y);Add(y,x);

	}

	bfs();

	for(re int i=1;i<n;++i)

	{

		int start=a[i],to=a[i+1],lca=LCA(start,to);

		if(i==1)

		{

			if(lca==start) {++cf[to];--cf[f[start][0]];continue;}

			if(lca==to) {++cf[start];--cf[f[to][0]];continue;}

			++cf[start];++cf[to];--cf[lca];--cf[f[lca][0]];continue;

		}

		if(i==n-1)

		{

			if(lca==start) {++cf[f[to][0]];--cf[start];continue;}

			if(lca==to) {++cf[f[start][0]];--cf[to];continue;}

			++cf[f[start][0]];++cf[f[to][0]];--cf[lca];--cf[f[lca][0]];continue;

		}

		if(lca==start) {++cf[to];--cf[start];continue;}

		if(lca==to) {++cf[f[start][0]];--cf[f[to][0]];continue;}

		++cf[f[start][0]];++cf[to];--cf[lca];--cf[f[lca][0]];

	}

	dfs(1);

	for(re int i=1;i<=n;++i) cout<<cf[i]<<endl;

	return 0;

}

巴特西

洛谷P3258 [JLOI2014]松鼠的新家【LCA+树上差分】

简要题意

题意分析

树上差分

LCA

最新文章

热门文章