自动搬运

查看原文

来自洛谷，原作者为

	密期望 **

搬运于2025-08-24 22:14:51，当前版本为作者最后更新于2020-01-19 16:18:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

时间复杂度：$O(n+m)$且不需要$O(1)LCA$

思路与我发的简化版题目题解类似，记录每个询问的top即可。但由于这里有多种颜色，所以我们只能离线询问，对每个节点上挂的询问分别处理。

#include<cstdio>
#include<vector>
using std::vector;
typedef long long ll;
typedef long double ld;
const int N=1e5+10;
void file(const char *str){
    char in[100],out[100];
    sprintf(in,"%s.in",str),sprintf(out,"%s.out",str);
    freopen(in,"r",stdin),freopen(out,"w",stdout);
}
#define fast_io
#ifdef fast_io
const int _IB=1e6;
char _ibuf[_IB],*_s,*_t;
#define getchar()\
 (_s==_t&&(_t=(_s=_ibuf)+fread(_ibuf,1,_IB,stdin),_s==_t)?EOF:*_s++)
#endif
ll read(){
    ll a=0;int op=1;char ch=getchar();
    while(ch<'0'||'9'<ch){if(ch=='-')op=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){a=(a<<3)+(a<<1)+(48^ch);ch=getchar();}
    return a*op;
}
struct L{
    int to,next;
};
int head[N];
L l[N<<1];
int lcount;
void add(int from,int to){
    l[++lcount].to=to;
    l[lcount].next=head[from];
    head[from]=lcount;
}
#define REPL(S,I,T) for(int I=head[S],T;T=l[I].to,I;I=l[I].next)
int n,m;
int c[N];
int top[N];
int q[N];
int ans[N];
vector<int>mount[N];
void dfs(int now=1,int f=0){
    int buf=top[c[now]];
    for(int i=0;i<(int)mount[now].size();i++){
#define x mount[now][i]
        if(~ans[x]){
            ans[x]=(top[q[x]]!=ans[x]);
        }else{
            ans[x]=top[q[x]];
        }
#undef x
    }
    REPL(now,i,to)if(to!=f){
        top[c[now]]=to;
        dfs(to,now);
    }
    top[c[now]]=buf;
}
void input(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++)c[i]=read();
    int p1,p2;
    for(int i=1;i<n;i++){
        p1=read();
        p2=read();
        add(p1,p2);
        add(p2,p1);
    }
    for(int i=0;i<m;i++){
        p1=read();
        p2=read();
        q[i]=read();
        if(c[p1]==q[i]||c[p2]==q[i]){
            ans[i]=1;
        }else{
            ans[i]=-1;
            mount[p1].push_back(i);
            mount[p2].push_back(i);
        }
    }
}
void ini(){
}
void solve(){
    dfs();
}
void output(){
    for(int i=0;i<m;i++)printf("%d",ans[i]);
}
void test(){
    input();
    ini();
    solve();
    output();
}
void all(){
    file("tmp");
    test();
}
int main(){
    all();
    return 0;
}

吐槽一句：一个写了$O(nlog^2n)$算法的人为什么会有自信说别人数据结构学傻了？