LCA+差分【CF191C】Fools and Roads

Description

有一颗 \(n\) 个节点的树，\(k\) 次旅行，问每一条边被走过的次数。

Input

第一行一个整数 \(n\) （\(2\leq n\leq 10^5\)）。

接下来 \(n-1\) 行，每行两个正整数 \(x,y\) （\(1\leq x,y\leq n,x\neq y\)），表示 \(x\)与 \(y\) 之间有一条连边。

接下来一个整数 \(k\) （\(0\leq k\leq 10^5\) ）。

接下来 \(k\) 行，每行两个正整数 \(x,y\) （\(1\leq x,y\leq n\) ），表示有一个从 \(x\) 到 \(y\) 的旅行。

Output

共\(n-1\)个整数,中间由一个空格隔开。

这不是一道裸的边差分 emmm.

不过是输出一下每条边的被经过次数罢了。

不了解树上差分的来这里

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#define int long long

#define R register

using namespace std;

const int gz=1e5+8;

inline void in(int &x)

{

	int  f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int head[gz],tot,ans[gz],n,k;

struct cod{int u,v;}edge[gz<<1];

inline void add(R int x,R int y)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	head[x]=tot;

}

int depth[gz],f[gz][21],cnt[gz];

void dfs(R int u,R int fa)

{

	f[u][0]=fa;depth[u]=depth[fa]+1;

	for(R int i=1;(1<<i)<=depth[u];i++)

		f[u][i]=f[f[u][i-1]][i-1];

	for(R int i=head[u];i;i=edge[i].u)

	{

		if(edge[i].v==fa)continue;

		dfs(edge[i].v,u);

	}

}

inline int lca(R int x,R int y)

{

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

	for(R int i=20;i>=0;i--)

		if(depth[x]+(1<<i)<=depth[y])

			y=f[y][i];

	if(x==y)return y;

	for(R int i=20;i>=0;i--)

	{

		if(f[x][i]==f[y][i])continue;

		x=f[x][i],y=f[y][i];

	}

	return f[x][0];

}

void dfs2(R int u,R int fa)

{

	for(R int i=head[u];i;i=edge[i].u)

	{

		if(edge[i].v==fa)continue;

		dfs2(edge[i].v,u);

		cnt[u]+=cnt[edge[i].v];

		ans[(i+1)>>1]=cnt[edge[i].v];

	}

}

signed main()

{

	in(n);

	for(R int i=1,x,y;i<n;i++)

	{

		in(x),in(y);

		add(x,y);add(y,x);

	}

	dfs(1,0);

	in(k);

	for(R int i=1,x,y;i<=k;i++)

	{

		in(x),in(y);

		R int la=lca(x,y);

		cnt[x]++,cnt[y]++,cnt[la]-=2;

	}

	dfs2(1,0);

	for(R int i=1;i<n;i++)printf("%lld ",ans[i]);

}

巴特西

LCA+差分【CF191C】Fools and Roads

Description

Input

Output

最新文章

热门文章