海州区建设局网站,房屋装修设计软件哪个好用,广西南宁相亲网,宁波网站关键词优化代码题目
给出 n 个点的一棵树#xff0c;多次询问两点之间的最短距离。
注意#xff1a;
边是无向的。所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数#xff0c;m 表示询问次数#xff1b;
下来 n−1 行#xff0c;每行三个整数 x,y,k多次询问两点之间的最短距离。
注意
边是无向的。所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数m 表示询问次数
下来 n−1 行每行三个整数 x,y,k表示点 x 和点 y 之间存在一条边长度为 k
再接下来 m 行每行两个整数 x,y表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行对于每次询问输出一行询问结果。
数据范围
2 ≤ n ≤ 10^4 1 ≤ m ≤ 2 × 10^4 0 k ≤ 100 1 ≤ x , y ≤ n
思路 我们以以下样例来建一张图
样例
10 0
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10首先我们假定点1为根节点求出所有节点到点1的最短距离dist[ j ]。 我们可以假设点1为根节点往下深度优先遍历每一个节点只有当某一个节点的所有子节点都被便利之后才会更新其祖先节点所以在这个点 a 的所有子节点没有遍历结束之前 a 的所有子节点的祖先都是节点 a 。易得当求的两个点 x , y 都是属于点 a 的孙子结点的时候x与y的距离为dist[ i ] dist[ j ] - dist[ a ] * 2;
代码
#includebits/stdc.h
using namespace std;
typedef pairint,int PII;
const int N 20010, M N * 2;int n,m;
int h[N],e[M],w[M],ne[M],idx;
int res[N];
int dist[N];
int st[N];
int p[N];
vectorPII query[N];void add(int a,int b,int c)// 加点函数使用邻接表储存该图
{e[idx] b,ne[idx] h[a],w[idx] c,h[a] idx ;
}int find(int x)// 并查集板子
{if(p[x] ! x) p[x] find(p[x]);return p[x];
}void dfs(int u,int fa)// 初始每个点到根节点的距离
{for(int i h[u]; ~i ; i ne[i]){int j e[i];if(j fa) continue;// 因为是无向边所以会有一条边指向该点的父节点。dist[j] dist[u] w[i];// 子节点距离根节点的距离为父节点加上父节点到该点的距离dfs(j,u);//使用该点继续初始其他节点}
}void tarjan(int u)// 该题核心函数
{st[u] 1;for(int i h[u];~i; i ne[i])// 每个点的祖先都是它的父节点{int j e[i];if(!st[j]){tarjan(j);// 以j为祖先节点遍历所有j的所有子节点p[j] u;//将点j的所有子节点遍历完成之后就更新点j的祖先节点}}for(auto item : query[u]){int y item.first,id item.second;if(st[y] 2)// 如果点y已经完成遍历则可以进行求距离操作{int anc find(y);res[id] dist[u] dist[y] - dist[anc] * 2;}}st[u] 2;//表示该点祖先节点已经更新且所有子节点都已经完成遍历
}int main()
{cin n m;memset(h,-1,sizeof(h));for(int i 1; i n; i )//输入n-1条无向边{int a,b,c;cin a b c;add(a,b,c),add(b,a,c);}for(int i 0; i m; i )//输入m个询问{int a,b;cin a b;if(a b) continue;query[a].emplace_back(b,i);query[b].emplace_back(a,i);}for(int i 1; i n; i ) p[i] i;// 并查集初始化每个点所属的集合dfs(1,-1);// 假设点1为该树的根节点tarjan(1);for(int i 0; i m; i ) cout res[i] endl;return 0;
}
