题解 P5836 【[USACO19DEC]Milk Visits(silver)】
密期望
·
·
题解
即是只用了10min不到，由大常数选手编写，O(n)还是毫无悬念拿了最优解。
大家都把问题想复杂了，这题根本用不到lca。
为什么这道题特意只给了两种颜色？
因为只有两种颜色时，想要输出0，必须是一条路径上全都是另一种颜色。因此我们把题目转化为了如何判断一条路径是否同色。
我们用top[i]表示i号点向上连续与它同色最多能走到哪里。即
top[i]=
top[father[i]],if(color[father[i]]==color[i])
i,if(color[father[i]]!=color[i])
那么路径i->j同色当且仅当top[i]==top[j]
```
#include<cstdio>
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;
}
int read_color(){
char c;
while((c=getchar())!=EOF){
switch(c){
case 'H':return 0;
case 'G':return 1;
}
}
return -1;
}
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];
void dfs(int now=1,int t=1,int f=0){
top[now]=t;
REPL(now,i,to)if(f!=to)dfs(to,c[to]==c[now]?t:to,now);
}
void input(){
n=read();
m=read();
for(int i=1;i<=n;i++)c[i]=read_color();
int p1,p2;
for(int i=1;i<n;i++){
p1=read();
p2=read();
add(p1,p2);
add(p2,p1);
}
}
void ini(){
dfs();
}
void solve(){
int p1,p2,p3;
for(int i=0;i<m;i++){
p1=read();
p2=read();
p3=read_color();
printf("%d",c[p1]==p3||c[p2]==p3||top[p1]!=top[p2]?1:0);
}
}
void output(){
}
void test(){
input();
ini();
solve();
output();
}
void all(){
file("tmp");
test();
}
int main(){
all();
return 0;
}
```