2019CSUST集训队选拔赛题解(二)

时间:2022-12-20 23:07:54

凛冬将至

 

Description

维斯特洛大陆的原住民是森林之子,他们长得如孩童一般,善于使用石器,威力值35,用树叶树枝作为衣物,在森林里繁衍生息,与万物和平相处。他们会使用古老的魔法(比如绿之视野),威力值55。后来先民从维斯特洛大陆架登陆,凭借手中的青铜兵器和战马大举入侵,威力值分别是35和55。森林之子凭借魔法顽强抵抗,并冒险利用龙晶制造出了一个神奇的强悍的物种——异鬼,威力值60。双方持久不下之时签订了和平协议,先民占据了维斯特洛大陆,森林之子只保有森林。

七大王国如火如荼兴起之时,在遥远海洋的另一端,一个神秘的家族悄然兴起——坦格利安家族。此家族拥有三条巨龙,威力值90+,经过一个世纪的备战,在领导者伊耿一世的带领下乘龙入侵维斯特洛大陆。

借助龙的力量,伊耿一世很快统一了维斯特洛的七大王国,建立了空前强大的坦格利安王朝,像所有外来入侵者一样,坦格利安家族摒弃了龙的信仰开始信仰七神,并且将龙由放养改为圈养,再加上坦格利安家族为了保持血统纯正,实行近亲婚姻,生出来的继承者精神病人越来越多,这导让坦格利安王朝开始了眼花缭乱的花样作死之旅。

众(wo)所(xia)周(che)知(de),当凯特琳·徒利得知自己女儿艾莉亚逃到赫伦堡后,非常担心女儿的安全。假设维斯特洛大陆共有n个城市,共有n1条双向道路把这n个城市连接起来。也就是说这是一棵树。凯特琳想尽快临冬城赶到赫伦堡。除了已知的n-1条边外,凯特琳还知道一条额外的秘密路径(也是双向的):端点是是城市x和城市y,路径长度是z。现在想考考寒假过后的你有没有刷过题,问你Q个问题,每个问题给出临冬城(凯特琳所在城市)和赫伦堡(艾莉亚所在城市)的坐标,请你告诉凯特琳从临冬城到赫伦堡的最短路径长度是多少?

 

Input

第一行一个整数n(1n100000)

以下n1行描述一颗树,每行u,v,w表示一条从uv长为w的路径,u!=v

下一行三个整数x,y,z,意义如题(1x,yn,x!=y)。

下一行一个整数Q(100000)

以下Q行两个数字U,V代表临冬城和赫伦堡的坐标。

1w,z10000

 

Output

对每次询问输出从临冬城到赫伦堡的最短路径长度。

 

 

题目中所描述的是一颗

这里再提一下树的特点:

①每个点都联通

②不含圈

③n阶树有n-1条边

 

PS:特别的是,具备以上任何两个特点可推出第三个

 

要注意求树上两点的距离不能最短路算法,一般用LCA(只会这个

 

该题在树的基础上另加了一条边 只需要分情况讨论这条边对原有树的影响即可

故该题解法:裸LCA+分类讨论

 

ACODE:

 

//7777777 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<string> #include<queue> #include<utility> #include<vector> #define lson l , m , rt << 1 #define rson m+1 , r , rt << 1 | 1 #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double pi = 3.1415926535; const double eps = 1e-6; const int MX = 1e5 + 7; const int maxbit = 18; const double val = pi/180.0; const int INF = 0x3f3f3f3f; struct edge { int to; int val; }; int father[MX][maxbit]; int depth[MX]; int dis[MX]; int lg[MX]; vector<edge> G[MX]; void dfs(int nowp,int fa) { depth[nowp] = depth[fa] + 1; father[nowp][0] = fa; for(int j = 1;j <= lg[depth[nowp]] + 1;++j) { father[nowp][j] = father[father[nowp][j-1]][j-1]; } for(int i = 0;i < G[nowp].size();++i) { edge e = G[nowp][i]; if(e.to != fa) { dis[e.to] = dis[nowp] + e.val; dfs(e.to,nowp); } } } int lca (int u,int v) { if(depth[u] < depth[v]) swap(u,v); while(depth[u] != depth[v]) u = father[u][lg[depth[u] - depth[v]]]; if(u == v) return u; for(int j = lg[depth[u]];j >= 0;--j) { if(father[u][j] != father[v][j]){ u = father[u][j]; v = father[v][j]; } } return father[u][0]; } //对大常数的优化 void init() { lg[0] = -1; for(int i = 1;i < MX;++i) lg[i] = lg[i >> 1] + 1; } int main(int argc, char const *argv[]) { int n; int u,v,w; init();//记得初始化 scanf("%d",&n); for(int i = 1;i <= n-1;++i) { scanf("%d%d%d",&u,&v,&w); //邻接表建图  G[u].push_back({v,w}); G[v].push_back({u,w}); } dfs(1,0); scanf("%d%d%d",&u,&v,&w); int m; scanf("%d",&m); while(m--) { int x,y; scanf("%d%d",&x,&y); //三种情况 int p = lca(x,y); int ans = (dis[x] - dis[p]) + (dis[y] - dis[p]); int p1 = lca(x,u); int p2 = lca(y,v); int alt1 = (dis[x] - dis[p1]) + (dis[u] - dis[p1]); int alt2 = (dis[y] - dis[p2]) + (dis[v] - dis[p2]); ans = min(ans,alt1 + alt2 + w); p1 = lca(x,v); p2 = lca(y,u); alt1 = (dis[x] - dis[p1]) + (dis[v] - dis[p1]); alt2 = (dis[y] - dis[p2]) + (dis[u] - dis[p2]); ans = min(ans,alt1 + alt2 + w); printf("%d\n",ans); } return 0; }

 

 

以后千万不能带个错误的LCA板子了