Misha, Grisha and Underground

题意: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 ;
}

最新文章

  1. npm更新到最新版本的方法
  2. 在Web Api中集成protobuf
  3. HTML5桌面通知:notification
  4. centos6 pyotp bug修复
  5. js实现身份证号码验证
  6. 上下联动,右侧按钮过多poper展示
  7. hdu 4897 Little Devil I
  8. sprint3(第八天)
  9. 修改TrustedInstaller权限文件(无法删除文件)
  10. python echo服务器和客户端(客户端可以用telnet之类的)
  11. Python: 函数参数小结
  12. JavaScript arguments类数组
  13. JAVA $ JSP
  14. Python中if __name__==&quot;__main__&quot; 语句在调用多进程Process过程中的作用分析
  15. 039、Data Volume 之 bind mount (2019-02-28 周四)
  16. PyPDF2详解
  17. Spring Boot中Starter是什么
  18. k8s rc
  19. ueditor getshell漏洞重现及分析
  20. c#修改cpu主频

热门文章

  1. Log4Net 配置日志按日期和日志级别分类写入
  2. 计算机网络中IP地址和MAC地址
  3. 解决微信小程序开发者工具输入框焦点问题
  4. RocketMQ中Broker的刷盘源码分析
  5. 直方图均衡基本原理及Python实现
  6. Docker笔记(七):常用服务安装——Nginx、MySql、Redis
  7. cinder支持nfs快照
  8. javascript中的浅拷贝和深拷贝(拷贝引用和拷贝实例)
  9. 超实用,Linux中查看文本的小技巧
  10. HDU 4635 (完全图 和 有向图缩点)