题意重述
给定一棵无根树，每次给出 $a_i,b_i,c_i$，求 $a_i\sim b_i$ 的路径上是否存在一个点的权值为 $c_i$。
题意分析
首先这样一眼树链剖分，将一对多的非线性信息转化为线性信息后处理即可。
但是，本题还存在更简单的算法：倍增。
可以参考倍增 LCA，在从 $u,v$ 跳到 $\operatorname{lca}(u,v)$ 的过程中判断是否存在 $c_i$ 即可。
具体而言，就是设 $G[x][i],H[x][i]$ 表示 $x$ 至 $x$ 的 $2^i$ 级祖先的路径上是否存在 G、H。
其实也可以参考[NOIP2013 提高组]货车运输。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5,M=1e5;
struct edge{
int v,r;
}a[2*(N-1)+1];
int n,m,h[N+1],d[N+1],lg[N+1],f[N+1][__lg(N+1)+1];
bool vg[N+1],vh[N+1],G[N+1][__lg(N+1)+1],H[N+1][__lg(N+1)+1];
void create(int u,int v){
static int top;
a[++top]={v,h[u]};
h[u]=top;
}
void dfs(int x,int fx){
f[x][0]=fx;
G[x][0]=vg[x]||vg[fx];
H[x][0]=vh[x]||vh[fx];
d[x]=d[fx]+1;
for(int i=h[x];i>0;i=a[i].r){
if(a[i].v==fx)continue;
dfs(a[i].v,x);
}
}
void pre(){
for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)lg[i]--;
dfs(1,0);
for(int i=1;i<=lg[n];i++){
for(int x=1;x<=n;x++){
f[x][i]=f[f[x][i-1]][i-1];
G[x][i]=G[x][i-1]||G[f[x][i-1]][i-1];
H[x][i]=H[x][i-1]||H[f[x][i-1]][i-1];
}
}
}
bool query(int u,int v,char ch){
if(d[u]<d[v])swap(u,v);
for(int i=lg[d[u]-d[v]];i>=0;i--){
if(d[f[u][i]]>=d[v]){
switch(ch){
case 'G':
if(G[u][i])return true;
break;
case 'H':
if(H[u][i])return true;
break;
}u=f[u][i];
}
}if(u==v){
switch(ch){
case 'G':
if(vg[u]||vg[v])return true;
break;
case 'H':
if(vh[u]||vh[v])return true;
break;
}return false;
}
for(int i=lg[d[u]];i>=0;i--){
if(f[u][i]!=f[v][i]){
switch(ch){
case 'G':
if(G[u][i]||G[v][i])return true;
break;
case 'H':
if(H[u][i]||H[v][i])return true;
break;
}u=f[u][i],v=f[v][i];
}
}switch(ch){
case 'G':
if(G[u][0]||G[v][0])return true;
break;
case 'H':
if(H[u][0]||H[v][0])return true;
break;
}return false;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
char ch;
cin>>ch;
switch(ch){
case 'G':vg[i]=true;break;
case 'H':vh[i]=true;break;
}
}for(int i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
create(u,v);create(v,u);
}pre();
while(m--){
int x,y;
scanf("%d %d",&x,&y);
char ch;
cin>>ch;
printf("%d",query(x,y,ch));
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
