题意简述
求树上路径((u,v))上是否存在(H/G)
题目解析
一个比较明显的做法是用树上前缀和，用(H[i]/G[i])表示从根到(i)(H/G)的个数，处理询问的时候，(ans=H/G[u]+H/G[v]-H/G[lca]-H/G[f[lca]])（(lca)自己不能减去），类似于求(dis)的做法。
但是重点不是这个，我在题解区看到了一个更简单的做法，记录一下。
我们把颜色相同的，在树上有边相连的点连成一个连通块，用并查集维护。
那么同一个联通块里可以相互到达，并且不会经过另外一种牛奶。
所以如果查询的(u,v)在同一个连通块里，并且和连通块的牛奶不一样，那么就不高兴，否则会高兴。
►Code View Ver.1
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define LL long long
#define N 100005
#define DEL 100000
#define INF 0x3f3f3f3f
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48); c=getchar();}
return f*x;
}
int n,m,d;
char s[N];
vector<int>G[N];
int dep[N],f[N][20],h[N],g[N];
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
if(s[u]=='H') h[u]=1;
else g[u]=1;
h[u]+=h[fa],g[u]+=g[fa];
for(int i=1;i<=d;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
}
}
int LCA(int u,int v)
{
int tmp;
if(dep[u]<dep[v]) tmp=u,u=v,v=tmp;
for(int i=d;i>=0;i--)
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return u;
for(int i=d;i>=0;i--)
if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
int main()
{
n=rd(),m=rd();
d=1;
while((1<<d)<n) d++;
scanf("%s",s+1);
for(int i=1;i<=n-1;i++)
{
int u=rd(),v=rd();
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
char pfer[5];
while(m--)
{
int u=rd(),v=rd();
scanf("%s",pfer);
int lca=LCA(u,v),val;
if(pfer[0]=='H') val=h[u]+h[v]-h[lca]-h[f[lca][0]];
else val=g[u]+g[v]-g[lca]-g[f[lca][0]];
if(val) printf("1");
else printf("0");
}
return 0;
}
►Code View Ver.2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define LL long long
#define N 100005
#define DEL 100000
#define INF 0x3f3f3f3f
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48); c=getchar();}
return f*x;
}
int n,m;
char s[N];
vector<int>G[N];
int f[N];
int Find(int x)
{
if(f[x]==x) return x;
return f[x]=Find(f[x]);
}
void Union(int u,int v)
{
u=Find(u),v=Find(v);
if(u<v) f[u]=v;
else f[v]=u;
}
void Init()
{
for(int i=1;i<=n;i++)
f[i]=i;
}
int main()
{
n=rd(),m=rd();
scanf("%s",s+1);
Init();
for(int i=1;i<=n-1;i++)
{
int u=rd(),v=rd();
if(s[u]==s[v]) Union(u,v);
}
while(m--)
{
int u=rd(),v=rd();
char pfer[5];
scanf("%s",pfer);
u=Find(u),v=Find(v);
if(u==v&&s[u]!=pfer[0]) printf("0");
else printf("1");
}
return 0;
}