代码求调，TLE第9,10两个点，写写宝子们了
查看原帖
代码求调，TLE第9,10两个点，写写宝子们了
990145
IKUNsomse楼主2024/7/15 21:37
using namespace std;
const int INF=0x3f3f3f3f;
const int inf=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
#define pb(i) push_back(i)
#define fup(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
using vi = vector<int>;
using vvi = vector<vector<int>>;
using mi = map<int,int>;
using namespace std;


bitset<40010>bit[305][305];
bitset<40010>B;
struct Link_Cut_Tree{
    struct node{
        int fa,ch[2],size=1,virtual_size,color,sum,lazy,val;
    };vector<node>tree;
    Link_Cut_Tree(){}
    ~Link_Cut_Tree(){}
    Link_Cut_Tree(int n){
        tree=vector<node>(n+10);
    }
    bool ident(int x,int f){
        return tree[f].ch[1]==x;
    };
    bool isroot(int x){
        return tree[tree[x].fa].ch[0]!=x&&tree[tree[x].fa].ch[1]!=x;
    };
    void reverse(int x){
        tree[x].lazy^=1;
        swap(tree[x].ch[0],tree[x].ch[1]);
    };
    void pushup(int x){
        tree[x].sum=tree[x].val;
        if(tree[x].ch[0])tree[x].sum|=tree[tree[x].ch[0]].sum;
        if(tree[x].ch[1])tree[x].sum|=tree[tree[x].ch[1]].sum;
    };
    void pushdown(int x){
        if(tree[x].lazy){
            if(tree[x].ch[0]){
                reverse(tree[x].ch[0]);
            }
            if(tree[x].ch[1]){
                reverse(tree[x].ch[1]);
            }
            tree[x].lazy^=1;
        }
    };
    void pushall(int x){
        if(!isroot(x)){
            pushall(tree[x].fa);
        }
        pushdown(x);
    };
    void connect(int x,int f,int k){
        tree[f].ch[k]=x;
        tree[x].fa=f;
    };
    void rotate(int x){
        int f=tree[x].fa,ff=tree[f].fa,fk=ident(x,f),ffk=ident(f,ff);
        connect(tree[x].ch[fk^1],f,fk);
        tree[x].fa=ff;
        if(!isroot(f)){
            tree[ff].ch[ffk]=x;
        }
        connect(f,x,fk^1);
        pushup(f);
        pushup(x);
    };
    void splay(int x){
        pushall(x);
        while(!isroot(x)){
            int f=tree[x].fa,ff=tree[f].fa;
            if(!isroot(f)){
                ident(x,f)^ident(f,ff)?rotate(x):rotate(f);
            }
            rotate(x);
        }
    };
    void access(int x){
        for(int y=0;x;x=tree[y=x].fa){
            splay(x);
            tree[x].ch[1]=y;
            pushup(x);
        }
    };
    void changeroot(int x){
        access(x);
        splay(x);
        reverse(x);
    };
    int findroot(int x){
        access(x);
        splay(x);
        int root=x;
        while(tree[root].ch[0]){
            pushdown(root);
            root=tree[root].ch[0];
        }
        splay(root);
        return root;
    };
    void link(int x,int y){
        changeroot(x);
        changeroot(y);
        if(findroot(y)==x)return;
        tree[x].fa=y;
    };
    bool split(int x,int y){
        if(findroot(x)!=findroot(y))return false;
        changeroot(x);
        access(y);
        splay(y);
        return true;
    }
    void changeval(int x,int val){
        changeroot(x);
        tree[x].val=val;
        tree[x].sum=val;
    };
    int getans(int x,int y){
        int cnt=0;
        B.reset();
        auto dfs=[&](auto self,int u)->void{
            if(!u)return;
            B.set(tree[u].color);
            self(self,tree[u].ch[0]);
            self(self,tree[u].ch[1]);
        };
        auto get=[&](auto self,int u)->int{
            if(tree[u].ch[1]&&tree[tree[u].ch[1]].sum)return self(self,tree[u].ch[1]);
            if(tree[u].val)return u;
            return self(self,tree[u].ch[0]);
        };
        split(x,y);
        if(tree[y].sum){
            int X=get(get,y);
            split(X,y);
            dfs(dfs,y);
            split(y,x);
            int Y=get(get,x);
            split(Y,x);
            dfs(dfs,x);
            B|=bit[tree[X].val][tree[Y].val];
        }else dfs(dfs,y);
        splay(x);
        return (int)B.count();
    };
};

void solve(){
    mt19937_64 Rand(random_device{}());
    int n,q;cin>>n>>q;
    vi val(n+10);
    mi id;
    fup(i,1,n,1)cin>>val[i];
    fup(i,1,n,1)id[val[i]]++;
    int idex=0;
    for(auto &[x,y]:id)y=++idex;
    fup(i,1,n,1)val[i]=id[val[i]];
    Link_Cut_Tree lct(n+10);
    fup(i,1,n,1)lct.tree[i].color=val[i];
    vvi adj(n+10);
    fup(i,2,n,1){
        int u,v;cin>>u>>v;
        lct.link(u,v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int M=min(n,(int)sqrt(n+1)+1);
    vi flag(n+10);
    iota(flag.begin(),flag.end(),0);
    shuffle(flag.begin()+1,flag.begin()+1+n,Rand);
    fup(i,1,M,1){
        lct.tree[flag[i]].val=i;
        lct.tree[flag[i]].sum=i;
    }
    vi cnt(n+10);
    fup(i,1,n,1){
        if(lct.tree[i].val){
            auto init=[&](auto self,int u,int f)->void{
                cnt[lct.tree[u].color]++;
                B.set(lct.tree[u].color);
                if(lct.tree[u].val){
                    bit[lct.tree[u].val][lct.tree[i].val]=B;
                    bit[lct.tree[i].val][lct.tree[u].val]=B;
                }
                for(auto &v:adj[u]){
                    if(v==f)continue;
                    self(self,v,u);
                }
                if(!--cnt[lct.tree[u].color])B.reset(lct.tree[u].color);
            };
            init(init,i,0);
        }
    }
    int lastans=0;
    while(q--){
        int x,y;cin>>x>>y;
        x^=lastans;
        cout<<(lastans=lct.getans(x,y))<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
}
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int inf=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
#define pb(i) push_back(i)
#define fup(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
using vi = vector<int>;
using vvi = vector<vector<int>>;
using mi = map<int,int>;
using namespace std;


bitset<40010>bit[305][305];
bitset<40010>B;
struct Link_Cut_Tree{
    struct node{
        int fa,ch[2],size=1,virtual_size,color,sum,lazy,val;
    };vector<node>tree;
    Link_Cut_Tree(){}
    ~Link_Cut_Tree(){}
    Link_Cut_Tree(int n){
        tree=vector<node>(n+10);
    }
    bool ident(int x,int f){
        return tree[f].ch[1]==x;
    };
    bool isroot(int x){
        return tree[tree[x].fa].ch[0]!=x&&tree[tree[x].fa].ch[1]!=x;
    };
    void reverse(int x){
        tree[x].lazy^=1;
        swap(tree[x].ch[0],tree[x].ch[1]);
    };
    void pushup(int x){
        tree[x].sum=tree[x].val;
        if(tree[x].ch[0])tree[x].sum|=tree[tree[x].ch[0]].sum;
        if(tree[x].ch[1])tree[x].sum|=tree[tree[x].ch[1]].sum;
    };
    void pushdown(int x){
        if(tree[x].lazy){
            if(tree[x].ch[0]){
                reverse(tree[x].ch[0]);
            }
            if(tree[x].ch[1]){
                reverse(tree[x].ch[1]);
            }
            tree[x].lazy^=1;
        }
    };
    void pushall(int x){
        if(!isroot(x)){
            pushall(tree[x].fa);
        }
        pushdown(x);
    };
    void connect(int x,int f,int k){
        tree[f].ch[k]=x;
        tree[x].fa=f;
    };
    void rotate(int x){
        int f=tree[x].fa,ff=tree[f].fa,fk=ident(x,f),ffk=ident(f,ff);
        connect(tree[x].ch[fk^1],f,fk);
        tree[x].fa=ff;
        if(!isroot(f)){
            tree[ff].ch[ffk]=x;
        }
        connect(f,x,fk^1);
        pushup(f);
        pushup(x);
    };
    void splay(int x){
        pushall(x);
        while(!isroot(x)){
            int f=tree[x].fa,ff=tree[f].fa;
            if(!isroot(f)){
                ident(x,f)^ident(f,ff)?rotate(x):rotate(f);
            }
            rotate(x);
        }
    };
    void access(int x){
        for(int y=0;x;x=tree[y=x].fa){
            splay(x);
            tree[x].ch[1]=y;
            pushup(x);
        }
    };
    void changeroot(int x){
        access(x);
        splay(x);
        reverse(x);
    };
    int findroot(int x){
        access(x);
        splay(x);
        int root=x;
        while(tree[root].ch[0]){
            pushdown(root);
            root=tree[root].ch[0];
        }
        splay(root);
        return root;
    };
    void link(int x,int y){
        changeroot(x);
        changeroot(y);
        if(findroot(y)==x)return;
        tree[x].fa=y;
    };
    bool split(int x,int y){
        if(findroot(x)!=findroot(y))return false;
        changeroot(x);
        access(y);
        splay(y);
        return true;
    }
    void changeval(int x,int val){
        changeroot(x);
        tree[x].val=val;
        tree[x].sum=val;
    };
    int getans(int x,int y){
        int cnt=0;
        B.reset();
        auto dfs=[&](auto self,int u)->void{
            if(!u)return;
            B.set(tree[u].color);
            self(self,tree[u].ch[0]);
            self(self,tree[u].ch[1]);
        };
        auto get=[&](auto self,int u)->int{
            if(tree[u].ch[1]&&tree[tree[u].ch[1]].sum)return self(self,tree[u].ch[1]);
            if(tree[u].val)return u;
            return self(self,tree[u].ch[0]);
        };
        split(x,y);
        if(tree[y].sum){
            int X=get(get,y);
            split(X,y);
            dfs(dfs,y);
            split(y,x);
            int Y=get(get,x);
            split(Y,x);
            dfs(dfs,x);
            B|=bit[tree[X].val][tree[Y].val];
        }else dfs(dfs,y);
        splay(x);
        return (int)B.count();
    };
};

void solve(){
    mt19937_64 Rand(random_device{}());
    int n,q;cin>>n>>q;
    vi val(n+10);
    mi id;
    fup(i,1,n,1)cin>>val[i];
    fup(i,1,n,1)id[val[i]]++;
    int idex=0;
    for(auto &[x,y]:id)y=++idex;
    fup(i,1,n,1)val[i]=id[val[i]];
    Link_Cut_Tree lct(n+10);
    fup(i,1,n,1)lct.tree[i].color=val[i];
    vvi adj(n+10);
    fup(i,2,n,1){
        int u,v;cin>>u>>v;
        lct.link(u,v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int M=min(n,(int)sqrt(n+1)+1);
    vi flag(n+10);
    iota(flag.begin(),flag.end(),0);
    shuffle(flag.begin()+1,flag.begin()+1+n,Rand);
    fup(i,1,M,1){
        lct.tree[flag[i]].val=i;
        lct.tree[flag[i]].sum=i;
    }
    vi cnt(n+10);
    fup(i,1,n,1){
        if(lct.tree[i].val){
            auto init=[&](auto self,int u,int f)->void{
                cnt[lct.tree[u].color]++;
                B.set(lct.tree[u].color);
                if(lct.tree[u].val){
                    bit[lct.tree[u].val][lct.tree[i].val]=B;
                    bit[lct.tree[i].val][lct.tree[u].val]=B;
                }
                for(auto &v:adj[u]){
                    if(v==f)continue;
                    self(self,v,u);
                }
                if(!--cnt[lct.tree[u].color])B.reset(lct.tree[u].color);
            };
            init(init,i,0);
        }
    }
    int lastans=0;
    while(q--){
        int x,y;cin>>x>>y;
        x^=lastans;
        cout<<(lastans=lct.getans(x,y))<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
}
2024/7/15 21:37