博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 4547(LCA)
阅读量:5878 次
发布时间:2019-06-19

本文共 2318 字,大约阅读时间需要 7 分钟。

题目链接:

思路:这题的本质还是LCA问题,但是需要注意的地方有:

1、如果Q中u,v的lca为u,那么只需一步u->...->v。

2、如果Q中u,v的lca为v,那么需abs(dist[u]  - dist[v])步。

3、否则以上情况都不满足,那么需abs(dist[v] - dist[lca(u, v)])+1步。

#include 
#include
#include
#include
#include
#include
using namespace std;const int MAX_N = (400000 + 20000);struct Edge { int v, next;} edge[MAX_N];int NE, cnt, head[MAX_N], Indegree[MAX_N];map
mp;void Init(){ mp.clear(); cnt = NE = 0; memset(head, -1, sizeof(head)); memset(Indegree, 0, sizeof(Indegree));}void Insert(int u, int v){ edge[NE].v = v; edge[NE].next = head[u]; head[u] = NE++;}struct q_edge { int u, v, id, next;} q_ee[MAX_N];int q_ne, q_head[MAX_N];void q_init(){ q_ne = 0; memset(q_head, -1, sizeof(q_head));}void q_insert(int u, int v, int id){ q_ee[q_ne].u = u; q_ee[q_ne].v = v; q_ee[q_ne].id = id; q_ee[q_ne].next = q_head[u]; q_head[u] = q_ne++;}int N, M, ans[MAX_N], dist[MAX_N];int parent[MAX_N], lca[MAX_N];bool vis[MAX_N];int Find(int x){ if (x == parent[x]) { return parent[x]; } return parent[x] = Find(parent[x]);}void dfs(int u){ parent[u] = u; vis[u] = true; for (int i = q_head[u]; ~i; i = q_ee[i].next) { int v = q_ee[i].v, id = q_ee[i].id; if (vis[v]) { lca[id] = Find(v); } } for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; if (!vis[v]) { dist[v] = dist[u] + 1; dfs(v); parent[v] = u; } }}int main(){ int Cas; cin >> Cas; while (Cas--) { cin >> N >> M; Init(); for (int i = 1; i < N; ++i) { string str1, str2; cin >> str1 >> str2; if (mp.find(str1) == mp.end()) mp[str1] = ++cnt; if (mp.find(str2) == mp.end()) mp[str2] = ++cnt; Indegree[mp[str1]]++; Insert(mp[str2], mp[str1]); } q_init(); for (int i = 1; i <= M; ++i) { string str1, str2; cin >> str1 >> str2; q_insert(mp[str1], mp[str2], i); q_insert(mp[str2], mp[str1], i); } //from root; memset(vis, false, sizeof(vis)); for (int i = 1; i <= cnt; ++i) { if (!Indegree[i]) { dist[i] = 0; dfs(i); break; } } for (int i = 0; i < q_ne; ++i) { if (!(i & 1)) { if (q_ee[i].u == q_ee[i].v) { puts("0"); } else if (q_ee[i].u == lca[q_ee[i].id]) { puts("1"); } else if (q_ee[i].v == lca[q_ee[i].id]) { printf("%d\n", abs(dist[q_ee[i].v] - dist[q_ee[i].u])); } else { printf("%d\n", abs(dist[q_ee[i].u] - dist[lca[q_ee[i].id]]) + 1); } } } } return 0;}


转载地址:http://xfdix.baihongyu.com/

你可能感兴趣的文章
ServlertContext
查看>>
eclipse编辑器生命周期事件监听
查看>>
Python WOL/WakeOnLan/网络唤醒数据包发送工具
查看>>
sizeof(long)
查看>>
pxe网络启动和GHOST网克
查看>>
2.5-saltstack配置apache
查看>>
http状态响应码大全(复制转帖)
查看>>
django数据库中的时间格式与页面渲染出来的时间格式不一致的处理
查看>>
Python学习笔记
查看>>
java String
查看>>
renhook的使用
查看>>
Linux学习笔记(十二)--命令学习(用户创建、删除等)
查看>>
DOCKER windows 7 详细安装教程
查看>>
养眼美女绿色壁纸
查看>>
U盘启动盘制作工具箱 v1.0
查看>>
增强myEclipse的提示功能
查看>>
Zabbix汉化方法
查看>>
Java I/O系统基础知识
查看>>
Java多线程设计模式(2)生产者与消费者模式
查看>>
基于whoosh的flask全文搜索插件flask-msearch
查看>>