题解 P5838 【[USACO19DEC]Milk Visits(gold)】
时间复杂度：
思路与我发的简化版题目题解类似，记录每个询问的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;
}吐槽一句：一个写了