救,样例过不了
查看原帖
救,样例过不了
797897
_QyGyQ_楼主2023/12/24 10:37
#include<bits/stdc++.h>
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
using ll=long long;
const int N=1e6+7;
vector<int>G[N];
int L[N],sum[N],a[N],R[N];
int tag[N<<2],tree[N<<2];
int n,q;
int cnt=0;
void dfs(int u,int fa){
	sum[++cnt]=u;
	L[u]=cnt;
	for(int i=0;i<G[u].size();i++){
		if(G[u][i]==fa) continue;
		dfs(G[u][i],u);
	}
	R[u]=cnt;
}
void add_tag(int p,int pl,int pr,int d){
	tag[p]+=d;
	tree[p]+=d*(pr-pl+1);
}
void push_up(int p){
	tree[p]=tree[lc(p)]+tree[rc(p)];
}
void push_down(int p,int pl,int pr){
	if(tag[p]){
		int mid=(pl+pr)>>1;
		add_tag(lc(p),pl,mid,tag[p]);
		add_tag(rc(p),mid+1,pr,tag[p]);
		tag[p]=0;
	}
}
void build(int p,int pl,int pr){
	if(pl==pr){
		tree[p]=a[sum[pl]];
		return ;
	}
	int mid=(pl+pr)>>1;
	build(lc(p),pl,mid);
	build(rc(p),mid+1,pr);
	push_up(p); 
}
void update(int L,int R,int p,int pl,int pr,int d){
	if(L<=pl&&pr<=R){
		add_tag(p,pl,pr,d);
		return;
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(L<=mid) update(L,R,lc(p),pl,mid,d);
	if(R>mid) update(L,R,rc(p),mid+1,pr,d);
	push_up(p);
}
int query(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R){
		return tree[p];
	}
	push_down(p,pl,pr);
	int res=0;
	int mid=(pl+pr)>>1;
	if(L<=mid){
		res+=query(L,R,lc(p),pl,mid);
	}
	if(R>mid){
		res+=query(L,R,rc(p),mid+1,pr);
	}
	return res;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++){
		int p;
		cin>>p;
		update(L[p],R[p],1,1,n,1);
	}
	for(int i=1;i<=n;i++){
		cout<<query(i,i,1,1,n)<<"\n";
	}
	return 0;
} 
2023/12/24 10:37
加载中...