1 条题解

  • 1
    @ 2023-7-21 11:41:21

    image

    #include<iostream>
    #define ll long long
    #define mod 998244353
    using namespace std;
    const int N=100005;
    int n,m,k,s,t,head[N],tot,a[N],c[N],x,sz[N],pos[N],ans[N];
    struct node{
    	int y,nex;
    }e[N<<1];
    void adde(int s,int t){
    	e[++tot]=(node){t,head[s]};
    	head[s]=tot;
    }
    void dfs(int u,int fa){
    	pos[u]=++tot;sz[u]=1;
    	for (int i=head[u];i;i=e[i].nex){
    		int v=e[i].y;
    		if (v==fa) continue;
    		dfs(v,u);
    		sz[u]+=sz[v];
    	}
    }
    void add(int x,int k){
    	for (;x<=n;x+=x&(-x)) c[x]+=k;
    }
    int query(int x){
    	int tmp=0;
    	for (;x;x-=x&(-x)) tmp+=c[x];
    	return tmp;
    }
    int main()
    {
    	cin>>n;
    	for (int i=1;i<n;++i) {
    		cin>>s>>t;
    		adde(s,t);
    		adde(t,s);
    	}
    	tot=0;dfs(1,0);
    	for (int i=1;i<=n;++i){
    		cin>>x;
    		cout<<query(pos[x])<<"\n";
    		add(pos[x],1);add(pos[x]+sz[x],-1);
    	}
    }
    
    
    
    • 1

    信息

    ID
    311
    时间
    1000ms
    内存
    125MiB
    难度
    2
    标签
    递交数
    43
    已通过
    29
    上传者