luogu5836 Milk Visits S

Farmer John 计划建造 N 个农场，用 N-1 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

Farmer John 的 MM 个朋友经常前来拜访他。在朋友 i 拜访之时，Farmer John 会与他的朋友沿着从农场 A_iAi? 到农场 B_iBi? 之间的唯一路径行走（可能有 A_i = B_i）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入的第一行包含两个整数 N 和 M。

第二行包含一个长为 N 的字符串。如果第i 个农场中的奶牛是更赛牛，则字符串中第 i 个字符为 G，如果第 i 个农场中的奶牛是荷斯坦牛则为 H。

以下 N-1 行，每行包含两个不同的整数 X 和 Y（1≤X,Y≤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。

在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

关于部分分：

测试点 1 样例。

测试点 2～5 满足 N≤10^3，M≤2?10^3。

对于 100% 的数据，1≤N≤10^5，1≤M≤10^5。

_______________________________________________

只有两种牛，所以把相同种类且相邻的牛看做一团，也就是一个点。用并查集维护！

如果查询的两头牛是不同的牛那么坑定能满足要求

如果相同的牛，那么看看他们是不是一个团（是否在一棵并查集树种）。不是同一棵树，那么他们中间可定有另一种牛隔开，那么也满足要求。

如果在一个团中，且是要求的那种牛，同样满足要求。否则不满足要求！

_______________________________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 int n,m;
 5 char s[maxn],ans[maxn];
 6 int f[maxn];
 7 int find(int x)
 8 {
 9     return f[x]==x?x:f[x]=find(f[x]);
10 }
11 void join(int x,int y)
12 {
13     x=find(x);y=find(y);
14     if(x!=y)
15     {
16         if(rand()%2)f[x]=y;
17         else f[y]=x;
18     }
19 }
20 int main()
21 {
22     scanf("%d%d",&n,&m);
23     scanf("%s",s+1);
24     for(int i=1;i<=n;++i)f[i]=i;
25     for(int u,v,i=1;i<n;++i)
26     {
27         scanf("%d%d",&u,&v);
28         if(find(u)!=find(v)&&s[u]==s[v])join(u,v);
29     }
30     char c;
31     for(int u,v,i=1;i<=m;++i)
32     {
33         scanf("%d%d %c",&u,&v,&c);
34         u=find(u);v=find(v);
35         if(u!=v||(u==v && s[u]==c))ans[i]=‘1‘;
36         else ans[i]=‘0‘;
37     }
38     puts(ans+1);
39     return 0;
40 }

View Code