Codeforces 832 D Misha, Grisha and Underground
2024-09-01 04:02:06
题意:Misha 和 Grisha 是2个很喜欢恶作剧的孩子, 每天早上 Misha 会从地铁站 s 通过最短的路到达地铁站 f, 并且在每个地铁站上都写上一句话, 然后Grisha 再从地铁站 t 通过最短的路到达地铁站 f, 并且记录下路途上被Misha写上字的地铁站数目,并且当天晚上会人会将地铁站清理干净,不会干扰第二天的计数, 现在给你3个地铁站 a, b, c, 现在求Misha记录的数目最大能是多少。
代码:求出Lca(a,b) Lca(a,c) Lca(b,c) 再找到深度最大的那个点, 我门可以通过画图发现 这个点是一个3叉路口, 从这个路口往每一地铁站走的路都是有效长度,最后找到有效长度就是答案了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+;
typedef pair<int,int> pll;
const int N = 1e5+;
struct Node{
int to;
int nt;
}e[N<<];
int head[N], anc[][N], deep[N];
int tot = ;
void add(int u, int v){
e[tot].to = v;
e[tot].nt = head[u];
head[u] = tot++;
}
void dfs(int u, int o){
deep[u] = deep[o] + ;
for(int i = head[u]; ~i; i = e[i].nt){
if(o != e[i].to){
anc[][e[i].to] = u;
for(int j = ; j < ; j++) anc[j][e[i].to] = anc[j-][anc[j-][e[i].to]];
dfs(e[i].to,u);
}
}
}
int lca(int u, int v){
if(deep[u] < deep[v]) swap(u, v);
for(int i = ; i >= ; i--) if(deep[v] <= deep[anc[i][u]]) u = anc[i][u];
if(u == v) return v;
for(int i = ; i >= ; i--) if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
return anc[][u];
}
int dis(int u, int v)
{
return deep[u]+deep[v]-*deep[lca(u,v)];
}
int main(){
int n, m, v;
scanf("%d%d", &n, &m);
memset(head, -, sizeof(head));
for(int i = ; i <= n; i++){
scanf("%d", &v);
add(i,v);
add(v,i);
}
dfs(,);
int a, b, c;
for(int i = ; i <= m; i++){
scanf("%d%d%d",&a,&b,&c);
int t1 = lca(a, b), t2 = lca(b,c), t3 = lca(a,c);
//cout << t1 <<' ' << t2 << ' ' << t3 << endl;
if(deep[t1] < deep[t2]) t1 = t2;
if(deep[t1] < deep[t3]) t1 = t3;
int ans = max3(dis(t1,a), dis(t1,b), dis(t1,c));
printf("%d\n",ans+);
}
return ;
}
最新文章
- npm更新到最新版本的方法
- 在Web Api中集成protobuf
- HTML5桌面通知:notification
- centos6 pyotp bug修复
- js实现身份证号码验证
- 上下联动,右侧按钮过多poper展示
- hdu 4897 Little Devil I
- sprint3(第八天)
- 修改TrustedInstaller权限文件(无法删除文件)
- python echo服务器和客户端(客户端可以用telnet之类的)
- Python: 函数参数小结
- JavaScript arguments类数组
- JAVA $ JSP
- Python中if __name__==";__main__"; 语句在调用多进程Process过程中的作用分析
- 039、Data Volume 之 bind mount (2019-02-28 周四)
- PyPDF2详解
- Spring Boot中Starter是什么
- k8s rc
- ueditor getshell漏洞重现及分析
- c#修改cpu主频