2019CSUST集训队选拔赛题解（二）
凛冬将至
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
Description
维斯特洛大陆的原住民是森林之子，他们长得如孩童一般，善于使用石器，威力值35，用树叶树枝作为衣物，在森林里繁衍生息，与万物和平相处。他们会使用古老的魔法（比如绿之视野），威力值55。后来先民从维斯特洛大陆架登陆，凭借手中的青铜兵器和战马大举入侵，威力值分别是35和55。森林之子凭借魔法顽强抵抗，并冒险利用龙晶制造出了一个神奇的强悍的物种——异鬼，威力值60。双方持久不下之时签订了和平协议，先民占据了维斯特洛大陆，森林之子只保有森林。
七大王国如火如荼兴起之时，在遥远海洋的另一端，一个神秘的家族悄然兴起——坦格利安家族。此家族拥有三条巨龙，威力值90+，经过一个世纪的备战，在领导者伊耿一世的带领下乘龙入侵维斯特洛大陆。
借助龙的力量，伊耿一世很快统一了维斯特洛的七大王国，建立了空前强大的坦格利安王朝，像所有外来入侵者一样，坦格利安家族摒弃了龙的信仰开始信仰七神，并且将龙由放养改为圈养，再加上坦格利安家族为了保持血统纯正，实行近亲婚姻，生出来的继承者精神病人越来越多，这导让坦格利安王朝开始了眼花缭乱的花样作死之旅。
众(wo)所(xia)周(che)知(de)，当凯特琳·徒利得知自己女儿艾莉亚逃到赫伦堡后，非常担心女儿的安全。假设维斯特洛大陆共有n个城市，共有n−1条双向道路把这n个城市连接起来。也就是说这是一棵树。凯特琳想尽快临冬城赶到赫伦堡。除了已知的n-1条边外，凯特琳还知道一条额外的秘密路径(也是双向的)：端点是是城市x和城市y，路径长度是z。现在想考考寒假过后的你有没有刷过题，问你Q个问题，每个问题给出临冬城(凯特琳所在城市)和赫伦堡(艾莉亚所在城市)的坐标，请你告诉凯特琳从临冬城到赫伦堡的最短路径长度是多少？
Input
第一行一个整数n(1≤n≤100000)。
以下n−1行描述一颗树，每行u,v,w表示一条从u到v长为w的路径，u!=v。
下一行三个整数x,y,z，意义如题（1≤x,y≤n,x!=y）。
下一行一个整数Q(100000)。
以下Q行两个数字U,V代表临冬城和赫伦堡的坐标。
1≤w,z≤10000
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板子了
