备案网站域名查询,搜索推广平台有哪些,鞍山制作公司网站的公司,重庆企业网站定制题目描述 给出 n 个点的一棵树#xff0c;多次询问两点之间的最短距离。 注意#xff1a;边是双向的。
输入描述 第一行为两个整数 n 和 m。n 表示点数#xff0c;m 表示询问次数#xff1b; 下来 n−1 行#xff0c;每行三个整数 x,y,k#xff0c;表示点 x 和点 y 之间…题目描述 给出 n 个点的一棵树多次询问两点之间的最短距离。 注意边是双向的。
输入描述 第一行为两个整数 n 和 m。n 表示点数m 表示询问次数 下来 n−1 行每行三个整数 x,y,k表示点 x 和点 y 之间存在一条边长度为 k 再接下来 m 行每行两个整数 x,y表示询问点 x 到点 y 的最短距离。
输出描述 输出 m 行。对于每次询问输出一行。
样例输入 2 2 1 2 100 1 2 2 1 样例输出 100 100 对于全部数据2≤ n n n≤ 1 0 4 10^4 104,1≤ m m m≤ 2 × 1 0 4 2×10^4 2×104,0 k k k≤ 100 100 100,1≤ x , y x,y x,y≤ n n n 首先这道题肯定是不能直接暴力跑的 但是换一个角度想这是一棵树先画个图 比如说我们要求3到4的距离 1我们先找出3和4的公共祖先——2 2把3的深度与4的深度加起来 3减去重复的部分根节点到最近公共祖先 求任意两点的距离大概就是这个思路 然后来看一个重要的数组—— f f f数组 f [ i ] f[i] f[i]表示的是节点 i i i的祖先节点 f i n d ( ) find() find()函数的作用就是找到祖先节点 后面就是dfs遍历节点同时找最近公共祖先
#includebits/stdc.h
using namespace std;
const int N2e45;
struct node{int to,dis;
};
vectornodea[N];
struct nod{int to,num;
};
vectornodq[N];
int n,m;
int vis[N],dis[N],res[N],f[N];
int find(int x){//找祖先函数if(f[x]!x)f[x]find(f[x]);return f[x];
}
void dfs(int x){vis[x]1;for(int i0;ia[x].size();i){//最近的公共祖先肯定要是最短路int va[x][i].to;int wa[x][i].dis;if(vis[v]0){dis[v]dis[x]w;dfs(v);f[v]x;}}for(int i0;iq[x].size();i){int toq[x][i].to;int numq[x][i].num;if(vis[to]2){res[num]dis[x]dis[to]-2*dis[find(to)];//计算距离}}vis[x]2;
}
signed main(){scanf(%d%d,n,m);for(int i1;in;i)f[i]i;for(int i1;in;i){int u,v,w;scanf(%d%d%d,u,v,w);a[u].push_back(node{v,w});a[v].push_back(node{u,w});}for(int i1;im;i){int x,y;scanf(%d%d,x,y);q[x].push_back(nod{y,i});q[y].push_back(nod{x,i});}dfs(1);for(int i1;im;i)printf(%d\n,res[i]);//离线输出
}最后祝程序员们节日快乐 ……祝方昳杨生日快乐…… 还有…… 对不起……
