題面

題目描述

Farmer John 計劃建造 \(N\)（\(1 \leq N \leq 10^5\)）個農場，用 \(N?1\) 條道路連接，構成一棵樹（也就是說，所有農場之間都互相可以到達，并且沒有環）。每個農場有一頭奶牛，品種為更賽牛或荷斯坦牛之一。

Farmer John 的 \(M\) 個朋友（\(1 \leq M \leq 10^5\)）經常前來拜訪他。在朋友 \(i\) 拜訪之時，Farmer John 會與他的朋友沿著從農場 \(A_i\) 到農場 \(B_i\) 之間的唯一路徑行走（可能有 \(A_i=B_i\)）。除此之外，他們還可以品嘗他們經過的路徑上任意一頭奶牛的牛奶。由于 Farmer John 的朋友們大多數也是農場主，他們對牛奶有著極強的偏好。他的有些朋友只喝更賽牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他們訪問時能喝到他們偏好的牛奶才會高興。

請求出每個朋友在拜訪過后是否會高興。

輸入

輸入的第一行包含兩個整數 \(N\) 和 \(M\)。

第二行包含一個長為 \(N\) 的字符串。如果第 \(i\) 個農場中的奶牛是更賽牛，則字符串中第 \(i\) 個字符為 G，如果第 \(i\) 個農場中的奶牛是荷斯坦牛則為 H。

以下 \(N?1\) 行，每行包含兩個不同的整數 \(X\) 和 \(Y\)（\(1 \leq X,Y \leq N\)），表示農場 \(X\) 與 \(Y\) 之間有一條道路。

以下 \(M\) 行，每行包含整數 \(A_i，B_i\)，以及一個字符 \(C_i\)。\(A_i\) 和 \(B_i\) 表示朋友 \(i\) 拜訪時行走的路徑的端點，\(C_i\) 是 G 或 H 之一，表示第 \(i\) 個朋友喜歡更賽牛的牛奶或是荷斯坦牛的牛奶。

輸出

輸出一個長為 \(M\) 的二進制字符串。如果第 \(i\) 個朋友會感到高興，則字符串的第 \(i\) 個字符為 1，否則為 0。

樣例輸入輸出

輸入：

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

這是筆者今天考試時的一道題，并非常蒟蒻地得了 \(56pts\)。

老師講完后頓有所悟，故作此篇。

\(P.S.\) 復制題面+改 \(\LaTeX\) 好煩。

思考

1. 考試時思路

考試時腦子一抽，覺得要用什么高大上的算法，估摸估摸有了個 LCA。

當時的想法是，記錄某個節點到根節點的“長度”，這里長度指的是把更賽牛看做 1，把荷斯坦牛看做 0，從某節點到根節點的所有節點的權值之和。然后詢問時先看路徑上有幾個點，再看路徑長度多少（LCA），然后比較一下。

最后，就得到了 \(56pts\) 的代碼：（代碼已丟失啊啊啊啊啊）

2. 老師講思路

就……標色法，DFS，碰到不同種類的牛就換種顏色繼續標……踢死就是所有想通的同種類的牛標記為同一種顏色（哇我好蒻居然沒有想到）

于是，我興沖沖地提交了第一份代碼：

#include <bits/stdc++.h>
using namespace std;
 
const int MS=100005;
int n,m,col[MS];
int head[MS],nxt[MS*2],vet[MS*2],edgenum;
char s[MS];
void addedge(int u,int v) {
    vet[++edgenum]=v;
    nxt[edgenum]=head[u];
    head[u]=edgenum;
    return ;
}
void dfs(int u,int fa) {
    int p=0;
    for(int e=head[u];e;e=nxt[e]) {
        int v=vet[e];
        if(v==fa) continue;
        if(s[u]==s[v]) col[v]=col[u];
        else col[v]=col[u]+(++p);
        dfs(v,u);
    }
    return ;
}
char ans[MS];
 
int main() {
    scanf("%d%d%s",&n,&m,s+1);
    int x,y;
    for(int i=1;i<n;i++) {
        scanf("%d%d",&x,&y);
        addedge(x,y),addedge(y,x);
    }
    dfs(1,0);
    char ch;
    for(int i=0;i<m;i++) {
        scanf("%d%d",&x,&y);
        cin>>ch;
        if(col[x]!=col[y]||s[x]==ch) ans[i]='1';
        else ans[i]='0';
    }
    printf("%s\n",ans);
    return 0;
}

嗯嗯？為什么 \(31pts\)？其實很簡單~

3. 進一步思考

首先！我發現了一個問題：當上面的程序遇到如下樣例時，就會出 BUG 。

詢問：2 3 H？顯然，從 2 到 3 的路徑上是有 H 牛的（1）。但是為什么輸出 0 呢？

觀察一下，發現其實 2 和 3 兩點不應同為 1。為什么？因為它們并不相連。于是，我們對以上代碼進行優化，添加隨機數，使兩個節點顏色相同的概率大大降低。

以下是代碼：

#include <bits/stdc++.h>
using namespace std;

const int MS=100005;
typedef long long ll;
int n,m;
ll col[MS];
int head[MS],nxt[MS*2],vet[MS*2],edgenum;
char s[MS];
mt19937 rng(1234567);
void addedge(int u,int v) {
	vet[++edgenum]=v;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
	return ;
}
void dfs(int u,int fa) {
	for(int e=head[u];e;e=nxt[e]) {
		int v=vet[e];
		if(v==fa) continue;
		if(s[u]==s[v]) col[v]=col[u];
		else col[v]=col[u]+rng();
		dfs(v,u);
	}
	return ;
}
char ans[MS];

int main() {
	scanf("%d%d%s",&n,&m,s+1);
	int x,y;
	for(int i=1;i<n;i++) {
		scanf("%d%d",&x,&y);
		addedge(x,y),addedge(y,x);
	}
	dfs(1,0);
	char ch;
	for(int i=0;i<m;i++) {
		scanf("%d%d",&x,&y);
		cin>>ch;
		if(col[x]!=col[y]||s[x]==ch) ans[i]='1';
		else ans[i]='0';
	}
	printf("%s\n",ans);
	return 0;
}

（\(max 156ms\)）

完！