为什么WA……
查看原帖
为什么WA……
78891
Kether楼主2020/7/14 17:22

RT

//Date:
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstring>
//#include<>
using namespace std;
inline int read(){
	register int x;register char c(getchar());register bool k;
	//while((c<'0'||c>'9')&&c^'-')if((c=getchar())==EOF)exit(0);
	if(c^'-')x=c-'0',k=1;else x=0,k=0;
	for(c=getchar();c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	return k?x:((~x)+1);
}
struct Edge{
	int next,to;
}edge[200200];
int head[200200],num_edge=0;
void add(int from,int to){
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge;
}
int n,k;
int pre[1000100];
int a,b;
int a1[2000200],top=0;
bool vis[1000200]={};
int h[1000100];
int fa[1000100];
int fi[1000100];
int st[1000100][20];
int ans[1000100];
int a2[1000100][2];
void dfs1(int i,int hi){
	a1[++top]=i;
	st[top][0]=top;
	fi[i]=top;
	vis[i]=true;
	h[i]=hi;
	for(int e=head[i];e!=0;e=edge[e].next){
		if(!vis[edge[e].to]){
			fa[edge[e].to]=i;
			dfs1(edge[e].to,hi+1);
			a1[++top]=i;
			st[top][0]=top;
		}
	}
}
void dfs2(int i){
	ans[i]=pre[i];
	vis[i]=true;
	for(int e=head[i];e!=0;e=edge[e].next){
		if(!vis[edge[e].to]){
			dfs2(edge[e].to);
			ans[i]+=ans[edge[e].to];
		}
	}
}
int rmq(int a,int b){
	int t=(int)(log((double)b-a+1)/log(2.0));
	if(h[a1[st[a][t]]]>h[a1[st[b-(1<<t)+1][t]]])return st[a1[b-(1<<t)+1]][t];
	else return st[a][t];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
		a2[i][0]=a;
		a2[i][1]=b;
	}
	dfs1(1,1);
	for(int i=1;i<=19;i++){
		for(int j=1;j<=top-(1<<i)+1;j++){
			if(h[a1[st[j][i-1]]]>h[a1[st[j+(1<<(i-1))][i-1]]])st[j][i]=st[j+(1<<(i-1))][i-1];
			else st[j][i]=st[j][i-1];
		}
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&a,&b);
		pre[a]++,pre[b]++;
		a=fi[a],b=fi[b];
		if(a>b){
			int t=a;
			a=b;
			b=t;
		}
		pre[a1[rmq(a,b)]]-=2;
	}
	for(int i=1;i<=n;i++)vis[i]=false;
	dfs2(1);
	for(int i=1;i<n;i++){
		if(fa[a2[i][0]]==a2[i][1])printf("%d ",ans[a2[i][0]]);
		else printf("%d ",ans[a2[i][1]]);
	}
	return 0;
}
2020/7/14 17:22
加载中...