洛谷3128樹上差分

この問題は最後に尋ねるだけなので,uからvへの経路を修正するにはsum[u]+,sum[v]+,sum[lca(u,v)]−,sum[father[lca(u,v)]−−という差分というテクニックを利用することができる.これにより,sum値を一度dfsで底から上に移動することができ,O(n)の時間内に各点の値を最後に求めることができる.

#include
#include
#include
using namespace std;
#define maxn 50005
int pre[maxn*2],other[maxn*2],last[maxn];
int n,m,l,jump[maxn][17],dep[maxn],ans[maxn],sum[maxn];
bool vis[maxn];

void connect(int x,int y) 
{
	l++;
	pre[l]=last[x];
	last[x]=l;
	other[l]=y;
}	

void pre_dfs(int u) 
{
	vis[u]=1;
	for (int p=last[u];p;p=pre[p]) 
	{
		int v=other[p];
		if (vis[v]) continue;
		jump[v][0]=u;
		dep[v]=dep[u]+1;
		pre_dfs(v);
	}
}

void dfs(int u) 
{
	vis[u]=1;
	ans[u]=sum[u];
	for (int p=last[u];p;p=pre[p]) 
	{
		int v=other[p];
		if (vis[v]) continue;
		dfs(v);
		ans[u]+=ans[v];
	}
}

int lca(int u,int v)
{
	if (dep[u]=0;j--) 
		if (jump[u][j]!=jump[v][j]) 
		{
			u=jump[u][j];
			v=jump[v][j];	
		}
	return jump[u][0];
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i