题目描述
农夫约翰计划建造 $N$ 个农场,用 $N−1$ 条道路连接,构成一棵树(也就是说,所有农场之间都互相可以到达,并且没有环)。
每个农场有一头奶牛,品种为更赛牛或荷斯坦牛之一。
约翰的 $M$ 个朋友经常前来拜访他。
在朋友 $i$ 拜访之时,约翰会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走(可能有 $A_i=B_i$)。
除此之外,他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。
由于约翰的朋友们大多数也是农场主,他们对牛奶有着极强的偏好。
他的有些朋友只喝更赛牛的牛奶,其余的只喝荷斯坦牛的牛奶。
任何约翰的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。
请求出每个朋友在拜访过后是否会高兴。
输入格式
输入的第一行包含两个整数 $N$ 和 $M$。
第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个农场中的奶牛是更赛牛,则字符串中第 $i$ 个字符为 ‘G’,如果第 i 个农场中的奶牛是荷斯坦牛则为 ‘H’。
以下 $N−1$ 行,每行包含两个不同的整数 $X$ 和 $Y$,表示农场 $X$ 与 $Y$ 之间有一条道路。
以下 $M$ 行,每行包含整数 $A_i$,$B_i$,以及一个字符 $C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点,$C_i$ 是 G
或 H
之一,表示第 $i$ 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。
输出格式
输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴,则字符串的第 $i$ 个字符为 1
,否则为 0
。
数据范围
$1≤N,M≤10^5$,
$1≤X,Y≤N$
输入样例:
5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H
输出样例:
10110
样例解释
在这里,从农场 $1$ 到农场 $4$ 的路径包括农场 $1、2$ 和 $4$。所有这些农场里都是荷斯坦牛,所以第一个朋友会感到满意,而第二个朋友不会。
算法1
($LCA$) $O(n log n)$
一、样例
根据样例可以画出题目中的树。
二、与$LCA$的关系
(1) 判断朋友是否满意的条件
题目中说每个朋友需要在访问时喝到自己偏好的牛奶才会满意
那很明显,就是从题目中的$A_i$点到$B_i$点的路径中需要有第$i$个朋友所偏好的牛奶
(2) 路径
找到了题目中朋友满意的条件
那我们现在就应该思考一下路径是怎么走的
我们找到题目中说的
在朋友 $i$ 拜访之时,约翰会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走(可能有 $A_i=B_i$)。
所以排除最短路等算法
那唯一的路径怎么求出来呢
我们可以发现
这个唯一的路径其实就是从$A_i$开始,到$A_i$和$B_i$的最近公共祖先($LCA$)为中转点,最后到达$B_i$的路径。
三、如何求出路径中是否有朋友偏好的牛奶
根据上面我们推导出来的路径的表示方法,那我们可以发现
这个路径中的点我们在做$LCA$时都会遍历到
所以,我们可以边做$LCA$边判断是否有朋友所偏好的牛奶
实现方法$1$
我们可以开一个$st[N][K][3]$的数组
用法:
那么
$st[j][k][1]$ 表示从$j$往上走$2^k$步中所有的点是否含有$G$种牛奶
$st[j][k][2]$ 表示从$j$往上走$2^k$步中所有的点是否含有$H$种牛奶
到做$LCA$的时候就可以用这个判断是否有朋友所偏好的牛奶了
实现方法$2$
这个方法其实是比上面的方法$1$省一点空间的
我们可以把原来二维的$fa$数组改成三维
用法:
- 设$j$为一个点
- 设$k$为要往上走$2^k$步
- 设$i$为$fa$数组第三维
那么
$fa[j][k][0]$ 表示原本二维的$fa$数组表示的数
$fa[j][k][1]$ 表示从$j$往上走$2^k$步中所有的点是否含有$G$种牛奶
$fa[j][k][2]$ 表示从$j$往上走$2^k$步中所有的点是否含有$H$种牛奶
时间复杂度
倍增算法版的$LCA$算法是$O(n log n)$的
而且也没做多余的需要时间的处理
所以这道题的时间复杂度就为$O(n log n)$
参考文献
然后这里的代码用的是上面说的实现方法$2$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10,M = 2 * N,K = 19; // N为点数,M为边数,K为最多要跳2^K步
int n,m;
int depth[N],fa[N][K][3]; // depth 表示深度;fa上面有讲解
int h[N],e[M],ne[M],idx; // 邻接表存图
char type[N]; // 牛奶的种类
int q[N]; // 队列
void add(int a,int b){ // 邻接表加边函数
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void bfs(int root){ // bfs预处理深度和fa
memset(depth,0x3f,sizeof depth);
depth[0] = 0;
depth[root] = 1;
fa[root][0][0] = 0;
int hh = 0,tt = 0;
q[0] = root; // 以上和LCA模板几乎一样,不解释
while(hh <= tt){
int t = q[hh ++];
for(int i = h[t];~i;i = ne[i]){
int j = e[i];
if(depth[j] > depth[t] + 1){
depth[j] = depth[t] + 1;
q[++ tt] = j;
fa[j][0][0] = t;
if(type[t] == 'G') fa[j][0][1] = 1;
else if(type[t] == 'H') fa[j][0][2] = 1; // 更新从j跳到t的路径上的牛奶
for(int k = 1;k < K;k ++){
fa[j][k][0] = fa[fa[j][k - 1][0]][k - 1][0]; // 与LCA模板相似,多了第三维
fa[j][k][1] = (fa[j][k - 1][1]) || (fa[fa[j][k - 1][0]][k - 1][1]);
fa[j][k][2] = (fa[j][k - 1][2]) || (fa[fa[j][k - 1][0]][k - 1][2]); // 更新fa数组中出现的牛奶
}
}
}
}
}
bool lca(int a,int b,char c){ // LCA
int cow;
if(c == 'G') cow = 1; // 把char换成int
else cow = 2;
if(type[a] == c || type[b] == c) return true; // 如果出现这种牛奶了,返回true
if(depth[a] < depth[b]) swap(a,b); // 如果a在b的上面,交换a,b
for(int i = K - 1;i >= 0;i --){ // 将a移到与b的深度一样的地方
if(depth[fa[a][i][0]] >= depth[b]){
if(fa[a][i][cow]) return true; // 判断是否跳到了有合适牛奶的地方
a = fa[a][i][0];
if(type[a] == c) return true; // 判断的其实都差不多
}
}
if(a == b) return false;
for(int i = K - 1;i >= 0;i --){ // 一起往上跳,如果出现朋友想要的牛奶,返回true
if(fa[a][i][0] != fa[b][i][0]){
if(fa[a][i][cow]) return true;
if(fa[b][i][cow]) return true;
a = fa[a][i][0];
b = fa[b][i][0];
if(type[a] == c || type[b] == c) return true;
}
}
if(type[fa[a][0][0]] == c) return true; // 如果a,b的公共祖先是朋友想要的牛奶,返回true
return false; // 没有找到朋友想要的牛奶,返回false
}
int main(){
memset(h,-1,sizeof h); // 邻接表初始化
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++){
char x;
cin>>x;
type[i] = x;
}
for(int i = 1;i < n;i ++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a); // 加双向边
} // 以上为输入部分
bfs(1); // 预处理
for(int i = 1;i <= m;i ++){ // 处理m个询问
int a,b;
char x;
scanf("%d%d",&a,&b);
cin>>x;
if(lca(a,b,x)) printf("1");
else printf("0");
}
return 0;
}