萌新求调题
查看原帖
萌新求调题
291706
Unordered_OIer楼主2021/1/11 21:27

树上差分板子,不知道哪里写挂了,盯了好久都没查出来。。。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void writeln(ll x){write(x),putchar('\n');}
struct edge{ll to,nxt;}es[N<<1];
ll n,k,u[N],v[N],hd[N],tot,p[N][20],f[N],d[N];
inline void add(ll u,ll v){es[++tot]=(edge){v,hd[u]},hd[u]=tot;}
inline void dfs1(ll u,ll fa){
	p[u][0]=fa,d[u]=d[fa]+1;
	for(ll i=1;(1LL<<i)<=d[u];i++)
		p[u][i]=p[p[u][i-1]][i-1];
	for(ll i=hd[u],v;i;i=es[i].nxt)
		if((v=es[i].to)!=fa)dfs1(v,u);
}
inline ll lca(ll x,ll y){
	if(d[x]<d[y])swap(x,y);
	for(ll i=20;i>=0;i--)
		if(d[p[x][i]]<=d[y])
			x=p[x][i];
	if(x==y)return x;
	for(ll i=20;i>=0;i--)
		if(p[x][i]!=p[y][i])
			x=p[x][i],y=p[y][i];
	return p[x][0];
}
inline ll dfs2(ll u,ll fa){
	f[fa]+=f[u];
	for(ll i=hd[u],v;i;i=es[i].nxt)
		if((v=es[i].to)!=fa)dfs2(v,u);
}
int main(){
	n=read();
	for(ll i=1;i<n;i++){
		u[i]=read(),v[i]=read();
		add(u[i],v[i]),add(v[i],u[i]);
	}
	dfs1(1,0);
	k=read();
	for(ll i=1,x,y;i<=k;i++){
		x=read(),y=read();
		f[x]++,f[y]++;
		f[lca(x,y)]-=2;
	}
	dfs2(1,0);
	for(ll i=1;i<n;i++)
		write(f[d[u[i]]>d[v[i]]?u[i]:v[i]]),putchar(' ');
	puts("");
	return 0;
}
2021/1/11 21:27
加载中...