德州网站收录,免费数据库网站空间,对网站策划的看法,瀑布流 网站 php 源码[AHOI2008] 紧急集合 / 聚会
题目描述
欢乐岛上有个非常好玩的游戏#xff0c;叫做“紧急集合”。在岛上分散有 n n n 个等待点#xff0c;有 n − 1 n-1 n−1 条道路连接着它们#xff0c;每一条道路都连接某两个等待点#xff0c;且通过这些道路可以走遍所有的等待点…[AHOI2008] 紧急集合 / 聚会
题目描述
欢乐岛上有个非常好玩的游戏叫做“紧急集合”。在岛上分散有 n n n 个等待点有 n − 1 n-1 n−1 条道路连接着它们每一条道路都连接某两个等待点且通过这些道路可以走遍所有的等待点通过道路从一个点到另一个点要花费一个游戏币。
参加游戏的人三人一组开始的时候所有人员均任意分散在各个等待点上每个点同时允许多个人等待每个人均带有足够多的游戏币用于支付使用道路的花费、地图标明等待点之间道路连接的情况以及对话机用于和同组的成员联系。当集合号吹响后每组成员之间迅速联系了解到自己组所有成员所在的等待点后迅速在 n n n 个等待点中确定一个集结点组内所有成员将在该集合点集合集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏由你来选择集合点聪明的你能够完成这个任务帮助小可可赢得游戏吗
输入格式
第一行两个正整数 n n n 和 m m m分别表示等待点的个数等待点也从 1 1 1 到 n n n 进行编号和获奖所需要完成集合的次数。
随后 n − 1 n-1 n−1 行每行两个正整数 a , b a,b a,b表示编号为 a a a 和编号为 b b b 的等待点之间有一条路。
随后 m m m 行每行用三个正整数 x , y , z x,y,z x,y,z表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。
输出格式
输出共 m m m 行每行两个用空格隔开的整数 p , c p,c p,c。其中第 i i i 行表示第 i i i 次集合点选择在编号为 p p p 的等待点集合总共的花费是 c c c 个游戏币。
样例 #1
样例输入 #1
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6样例输出 #1
5 2
2 5
4 1
6 0提示
对于 40 % 40\% 40% 的数据 n ≤ 2 × 1 0 3 n\leq2\times10^3 n≤2×103 m ≤ 2 × 1 0 3 m\leq2\times 10^3 m≤2×103。
对于 100 % 100\% 100% 的数据 1 ≤ x , y , z ≤ n ≤ 5 × 1 0 5 1\leq x,y,z\leq n\leq 5\times10^5 1≤x,y,z≤n≤5×105 1 ≤ m ≤ 5 × 1 0 5 1\leq m\leq 5\times 10^5 1≤m≤5×105。
分析
LCA与树的分析由于题目中已经保证了是树而有三个标记点每次求任意两个的LCA而必定有两个相同即可得到一个最近的LCA在建树时求出深度用O1求出最近点的距离
代码
#include bits/stdc.h
using namespace std;
const int M6*1e5;
vectorint T[M];
int n,m,s;
struct LCA{static const int k25;int f[M][k1],d[M],dmax0;void init(int s){f[s][0]s;for(int i1;(1i)dmax;i)for(int j1;jn;j)f[j][i]f[f[j][i-1]][i-1];return;}int query(int x,int y){if(d[x]d[y]) swap(x,y);for(int ik;i0;i--) if(d[f[y][i]]d[x]) yf[y][i];if(xy) return x;for(int ik;i0;i--){if(f[x][i]!f[y][i])xf[x][i],yf[y][i];}return f[x][0];}void dfs(int u,int fa,int dep){if(d[u]) return;d[u]dep;f[u][0]fa;for(auto v:T[u]) {dfs(v,u,dep1);}dmaxmax(dmax,dep);return;}void finit(int s){memset(f,0,sizeof(f));memset(d,0,sizeof(d));dfs(s,s,1);init(s);}
}solve;
signed main(){ios::sync_with_stdio(false);cinnm;for(int i1,u,v;in;i){cinuv;T[u].push_back(v);T[v].push_back(u);}solve.finit(1);for(int i1,a,b,c;im;i){cinabc;int x1solve.query(a,b),x2solve.query(b,c),x3solve.query(a,c);if (x1x2){int ansabs(solve.d[x3]-solve.d[a])abs(solve.d[x3]-solve.d[c]);ansabs(solve.d[x1]-solve.d[b])abs(solve.d[x1]-solve.d[x3]);coutx3 ansendl;}else if(x1x3){int ansabs(solve.d[x2]-solve.d[c])abs(solve.d[x2]-solve.d[b]);ansabs(solve.d[x3]-solve.d[a])abs(solve.d[x3]-solve.d[x2]);coutx2 ansendl;}else{int ansabs(solve.d[x1]-solve.d[a])abs(solve.d[x1]-solve.d[b]);ansabs(solve.d[x2]-solve.d[c])abs(solve.d[x2]-solve.d[x1]);coutx1 ansendl;}}return 0;
}
