2621 树上距离
有一棵n个节点的无向树，每条边有一个边权，现在有q次询问，每次询问给出两个点，
求这两个点之间的简单路径上的边权和是多少。
如图所示的数据中：
1号节点和2号节点之间的距离为：2
2号节点和3号节点之间的距离为：2+2+3=7
输入
第1行：两个整数n和q,n表示这棵树的节点个数，q表示查询的次数。(1<=n,q<=1000) 第2行~第n行：每行有三个整数u,v,w，表示u与v之间有一条权值为w的边。(1<=w<=10000) 第n+1行~n+q行：每行有两个正整数x,y，表示要查询的两个点的编号。
讯享网输出
讯享网第1行-第q行：每行输出一个数，表示那要查询的两点之间的简单路径上的边权和。输入样例
4 2 2 1 2 4 3 2 1 4 3 1 2 3 2输出样例
讯享网2 7
模板代码：
#include<iostream> #include<string.h> #include<math.h> #include<set> #include<queue> #include<stdio.h> #include<algorithm> #define LL long long #define INF 0x3f3f3f3f #define ull unsigned long long /* #ifdef MYHOME freopen("input.txt", "r", stdin); #endif */ using namespace std; const int N = 2e5 + 100; const int M = 4e5 + 100; int head[N], edge[M], ver[M], Next[M], tot; int n, q, x, y, z; int deep[N], dist[N], dp[N][30], maxst; void add (int x, int y, int z) { ver[++tot] = y; edge[tot] = z; Next[tot] = head[x]; head[x] = tot; } void init (int x, int pre) { deep[x] = deep[ver[pre ^ 1]] + 1; dist[x] = dist[ver[pre ^ 1]] + edge[pre]; dp[x][0] = ver[pre ^ 1]; for (int i = 1; i <= maxst; i ++) { dp[x][i] = dp[dp[x][i - 1]][i - 1]; } for (int i = head[x]; i; i = Next[i]) { y = ver[i]; if(i == (pre ^ 1)) continue; init (y, i); } } int sol_lca(int x, int y) { if (deep[x] >= deep[y]) swap(x,y); for (int i=maxst; i >= 0; i--) { if (deep[dp[y][i]] >= deep[x]) { y = dp[y][i]; } } if (x == y) return x; for (int i=maxst; i >= 0; i--) { if (dp[x][i] != dp[y][i]) { x = dp[x][i]; y = dp[y][i]; } } return dp[x][0]; } int main () { #ifdef MYHOME freopen("input.txt", "r", stdin); #endif while (cin >> n >> q) { tot = 1; memset(head, 0, sizeof(head)); memset(Next, 0, sizeof(Next)); memset(deep, 0, sizeof(deep)); memset(dist, 0, sizeof(dist)); memset(dp, 0, sizeof(dp)); maxst = (int)log(n) / log(2) + 2; for (int i = 1; i < n; i++) { cin >> x >> y >> z; add (x, y, z); add (y, x, z); } init(1, 0); for (int i = 1; i <= q; i++) { cin >> x >> y; cout << dist[x] + dist[y] - 2 * dist[sol_lca(x, y)] << endl; } } return 0; }THE END;
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/74999.html