这题是不是可以$O(n+m)$

YellowBean_Elsa @ 2020-02-17 20:59:07

by SKTelecomT1_Faker @ 2020-02-17 21:00:45

Orz

by YellowBean_Elsa @ 2020-02-17 21:02:48

@IAMAKER ZRR loves U (She told me herself)

by SKTelecomT1_Faker @ 2020-02-17 21:04:01

@YellowBean That's irreevant to me.

by YellowBean_Elsa @ 2020-02-17 21:05:16

@IAMAKER correction: irrelevant

by Smile_Cindy @ 2020-02-17 21:05:17

@YellowBean

你开桶怎么算

我觉得最优应该是线段树合并

by YellowBean_Elsa @ 2020-02-17 21:06:19

@Alpha 开桶不是两遍 O(N) 的dfs就水过去了吗

by SKTelecomT1_Faker @ 2020-02-17 21:06:48

@YellowBean My hand slipped

by mrsrz @ 2020-02-17 21:07:03

@Alpha 树上差分

by YellowBean_Elsa @ 2020-02-17 21:08:18

我写的，这是 O((N+M)logN) 但主要是把时间浪费在 LCA 和 map 上了（应该用 Tarjan 求 LCA，map 换成 vector）

//coder: Feliks a Hacker of IOI == GM-YB an AKer of IMO
#include<bits/stdc++.h>
using namespace std;
const int N=320005;
int n,m;
inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}int v[N<<1],nex[N<<1],first[N],tot;
queue<int> q;
int d[N],fa[21][N],T;
inline void adde(int x,int y){
    v[++tot]=y;
    nex[tot]=first[x];
    first[x]=tot;
}namespace LCA{
    inline void bfs(){
        q.push(1);
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=first[x];i;i=nex[i]){
                int y=v[i];if(d[y])continue;
                d[y]=d[x]+1;q.push(y);fa[0][y]=x;
                for(int j=1;j<=T;j++)
                    fa[j][y]=fa[j-1][fa[j-1][y]];
            }
        }
    }inline int lca(int x,int y){
        if(x==y)return x;
        if(d[x]<d[y])swap(x,y);
        //d[x] > d[y]
        for(int i=T;i>=0;i--)
            if(d[fa[i][x]]>=d[y])x=fa[i][x];
        if(x==y)return x;
        for(int i=T;i>=0;i--)
            if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
        return fa[0][x];
    }
}using namespace LCA;
int w[N],cn[N],s[N],t[N],cm[N],ap[N<<1];
map<int,int> cf[N];
int ans[N];
void dfs(int x,int f){
    int cnt=ap[cn[x]];
    for(map<int,int>::iterator it=cf[x].begin();it!=cf[x].end();it++)
        ap[(*it).first]+=(*it).second;
    for(int i=first[x];i;i=nex[i]){
        int y=v[i];if(y==f)continue;
        dfs(y,x);
    }ans[x]+=ap[cn[x]]-cnt;
}
int main(){
    n=read(),m=read();
    T=(int)(log(n)/log(2.0))+1;
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        adde(x,y),adde(y,x);
    }d[1]=1;bfs();
    for(int i=1;i<=n;i++)w[i]=read(),cn[i]=d[i]+w[i];
    for(int i=1;i<=m;i++){
        s[i]=read(),t[i]=read();
        int p=lca(s[i],t[i]);
        cf[s[i]][d[s[i]]]++;
        cf[fa[0][p]][d[s[i]]]--;
    }dfs(1,0);
    for(int i=1;i<=n;i++)cn[i]=w[i]-d[i]+n,cf[i].clear();
    for(int i=1;i<=m;i++){
        int p=lca(s[i],t[i]),x=d[s[i]]-(d[p]<<1)+n;
        cf[t[i]][x]++;
        cf[p][x]--;
    }dfs(1,0);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

by 皎月半洒花 @ 2020-02-17 21:11:04

准确来说，还是要带 \log，因为几乎没有人并查集写的是真的反阿克曼函数，都是写的一个log的并查集