高雄市网站建设_网站建设公司_Redis_seo优化

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客

【题目来源】

洛谷：[P5836 USACO19DEC] Milk Visits S - 洛谷

【题目描述】

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

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

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

【输入】

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

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

以下N − 1 N-1N−1行，每行包含两个不同的整数X XX和Y YY（1 ≤ X , Y ≤ N 1 \leq X, Y \leq N1≤X,Y≤N），表示农场X XX与Y YY之间有一条道路。

以下M MM行，每行包含整数A i A_iAi​，B i B_iBi​，以及一个字符C i C_iCi​。A i A_iAi​和B i B_iBi​表示朋友i ii拜访时行走的路径的端点，C i C_iCi​是G或H之一，表示第i ii个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

【输出】

输出一个长为M MM的二进制字符串。如果第i ii个朋友会感到高兴，则字符串的第i ii个字符为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

【算法标签】

《洛谷 P5836 Milk Visits》 #搜索# #树形数据结构# #并查集# #最近公共祖先# #USACO# #2019#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;// N: 最大节点数, M: 最大边数(双向边)intn,m;// n: 节点数, m: 查询次数inth[N],e[M],ne[M],idx;// 邻接表存图intdep[N],fa[N][30];// dep: 节点深度, fa: 倍增数组queue<int>q;// BFS队列string ans;// 存储答案// 节点结构体structNode{intc;// 节点颜色: 0表示H, 1表示Gintcnt[2];// cnt[0]: 从根到该节点的H数量, cnt[1]: 从根到该节点的G数量}a[N];// 添加边voidadd(inta,intb){e[idx]=b;// 存储终点ne[idx]=h[a];// 插入到链表头部h[a]=idx++;}// DFS计算从根到每个节点的颜色前缀和voiddfs(intu,intfather){// 从父节点继承颜色计数a[u].cnt[0]=a[father].cnt[0];a[u].cnt[1]=a[father].cnt[1];// 当前节点的颜色计数+1a[u].cnt[a[u].c]++;// 遍历子节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];if(j==father)continue;// 跳过父节点dfs(j,u);}}// BFS预处理节点深度和倍增数组voidbfs(introot){// 初始化深度memset(dep,0x3f,sizeof(dep));// 初始化为无穷大dep[0]=0;// 虚拟节点0深度为0dep[root]=1;// 根节点深度为1q.push(root);while(!q.empty()){intt=q.front();q.pop();for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];if(dep[j]>dep[t]+1)// 如果j节点深度未更新{dep[j]=dep[t]+1;// 计算深度q.push(j);// j入队fa[j][0]=t;// j向上走2^0=1步到达父节点t// 递推计算fa[j][k]: j向上走2^k步到达的节点for(intk=1;k<=29;k++){// j向上走2^k = (j向上走2^(k-1))再向上走2^(k-1)fa[j][k]=fa[fa[j][k-1]][k-1];}}}}}// LCA倍增算法，计算节点x和节点y的最近公共祖先intlca(intx,inty){// 保证x为深度较大的节点if(dep[x]<dep[y])swap(x,y);// 步骤1: 把x向上跳到与y同一深度for(intk=29;k>=0;k--)// 从大到小尝试{if(dep[fa[x][k]]>=dep[y])// 如果跳2^k步后深度仍>=y的深度x=fa[x][k];// 跳上去}// 如果此时x和y相等，说明y是x的祖先if(x==y)returnx;// 步骤2: 两个节点同时向上跳，跳到lca的下一层for(intk=29;k>=0;k--){if(fa[x][k]!=fa[y][k])// 如果跳2^k后到达的节点不同{x=fa[x][k];y=fa[y][k];}}// 此时x和y的父节点就是lcareturnfa[x][0];}intmain(){// 初始化邻接表memset(h,-1,sizeof(h));// 输入节点数和查询次数cin>>n>>m;// 输入每个节点的颜色for(inti=1;i<=n;i++){charc;cin>>c;if(c=='H')a[i].c=0;// H用0表示elsea[i].c=1;// G用1表示}// 输入边，构建树for(inti=1;i<n;i++){intx,y;cin>>x>>y;add(x,y),add(y,x);// 无向图，添加双向边}// DFS计算从根节点到每个节点的颜色前缀和// 假设1是根节点dfs(1,0);// BFS预处理深度和倍增数组bfs(1);// 处理每个查询for(inti=1;i<=m;i++){intx,y;charz;cin>>x>>y>>z;// 计算x和y的最近公共祖先intl=lca(x,y);// 计算路径x-y上H的数量// 公式: cnt[x] + cnt[y] - 2*cnt[l] + (l的颜色)intcolor_h=a[x].cnt[0]+a[y].cnt[0]-2*a[l].cnt[0]+(a[l].c==0);// 计算路径x-y上G的数量intcolor_g=a[x].cnt[1]+a[y].cnt[1]-2*a[l].cnt[1]+(a[l].c==1);// 根据查询的颜色输出结果if((z=='H'&&color_h>0)||(z=='G'&&color_g>0))ans+="1";elseans+="0";}cout<<ans<<endl;return0;}

【运行结果】

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