Description
维斯特洛大陆的原住民是森林之子，他们长得如孩童一般，善于使用石器，威力值35，用树叶树枝作为衣物，在森林里繁衍生息，与万物和平相处。他们会使用古老的魔法（比如绿之视野），威力值55。后来先民从维斯特洛大陆架登陆，凭借手中的青铜兵器和战马大举入侵，威力值分别是35和55。森林之子凭借魔法顽强抵抗，并冒险利用龙晶制造出了一个神奇的强悍的物种——异鬼，威力值60。双方持久不下之时签订了和平协议，先民占据了维斯特洛大陆，森林之子只保有森林。
。。。
七大王国如火如荼兴起之时，在遥远海洋的另一端，一个神秘的家族悄然兴起——坦格利安家族。此家族拥有三条巨龙，威力值90+，经过一个世纪的备战，在领导者伊耿一世的带领下乘龙入侵维斯特洛大陆。
借助龙的力量，伊耿一世很快统一了维斯特洛的七大王国，建立了空前强大的坦格利安王朝，像所有外来入侵者一样，坦格利安家族摒弃了龙的信仰开始信仰七神，并且将龙由放养改为圈养，再加上坦格利安家族为了保持血统纯正，实行近亲婚姻，生出来的继承者精神病人越来越多，这导让坦格利安王朝开始了眼花缭乱的花样作死之旅。
。。。
众(wo)所(xia)周(che)知(de)，当凯特琳·徒利得知自己女儿艾莉亚逃到赫伦堡后，非常担心女儿的安全。假设维斯特洛大陆共有nn个城市，共有n-1n−1条双向道路把这nn个城市连接起来。也就是说这是一棵树。凯特琳想尽快临冬城赶到赫伦堡。除了已知的n-1n−1条边外，凯特琳还知道一条额外的秘密路径(也是双向的)：端点是是城市xx和城市yy，路径长度是zz。现在想考考寒假过后的你有没有刷过题，问你QQ个问题，每个问题给出临冬城(凯特琳所在城市)和赫伦堡(艾莉亚所在城市)的坐标，请你告诉凯特琳从临冬城到赫伦堡的最短路径长度是多少？
Input
第一行一个整数n(1leq nleq 100000)n(1≤n≤100000)。
以下n-1n−1行描述一颗树，每行u,v,wu,v,w表示一条从uu到vv长为ww的路径，u!=vu!=v。
下一行三个整数x,y,zx,y,z，意义如题（1leq x,yleq n, x!=y1≤x,y≤n,x!=y）。
下一行一个整数Q(100000)Q(100000)。
以下QQ行两个数字U,VU,V代表临冬城和赫伦堡的坐标。
1leq w,z leq 10001≤w,z≤1000
Output
对每次询问输出从临冬城到赫伦堡的最短路径长度。
Sample Input 1
6
1 2 2
1 3 4
2 6 3
3 4 1
3 5 10
3 6 6
3
1 4
2 5
3 2
Sample Output 1
5
16
6
Source
2019年集训队选拔赛
思路： 直接最短路肯定会T的。 注意题中提示“这是一棵树”，那么就可以转换为LCA问题。LCA最短路的基本模式：x = dis[a]+dis[b]-2*dis[lca(a,b)];但本题最后一条边是非树边（但我一直以为是任意一条边是非树边），那么就可以枚举到最后一条路的3种情况，（1）直接到达，（2）先经过非树边左节点（3）先经过非树边右节点。那么一共跑5次LCA寻找最优结果.不过我见过CF一道原题是用dijkstra弄最后一条边的，下次找找放上来对比一下。
#include <bits/stdc++.h>
using namespace std;
const double g=10.0,eps=1e-7;
const long long N=100000+10,inf=0x3f3f3f;
struct edge{
long long to,Next,w;
}e[N * 2];
long long dis[N],father[20][N],depth[N];
long long cnt,head[N],value[N];
void add(long long u,long long v,long long w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].Next=head[u];
head[u]=cnt++;
}
void dfs(long long u,long long f)
{
father[0][u]=f;
for(long long i=head[u];~i;i=e[i].Next)
{
long long To=e[i].to;
if(To!=f)
{
dis[To]=dis[u]+e[i].w;
depth[To]=depth[u]+1;
dfs(To,u);
}
}
}
void init(long long n)
{
depth[1]=1;
dis[1]=0;
dfs(1,-1);
for(long long i=1;i<20;i++)
for(long long j=1;j<=n;j++)
father[i][j]=father[i-1][father[i-1][j]];
}
long long lca(long long x,long long y)
{
if(depth[x]>depth[y])swap(x,y);
for(long long i=0;i<20;i++)
if((depth[y]-depth[x])>>i&1)
y=father[i][y];
if(x==y)return x;
for(long long i=19;i>=0;i--)
{
if(father[i][x]!=father[i][y])
{
x=father[i][x];
y=father[i][y];
}
}
return father[0][x];
}
int main()
{
long long t,n,m;
// cin>>n;
while(~scanf("%lld",&n))
{
cnt=0;
memset(head,-1,sizeof head);
for(long long i=1; i<n; i++)
{
long long a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
init(n);
scanf("%lld",&m);
while(m--)
{
long long a,b;
long long x,y,z;
scanf("%lld%lld",&a,&b);
x = dis[a]+dis[b]-2*dis[lca(a,b)];
y = dis[a]+dis[u]-2*dis[lca(a,u)] + dis[v]+dis[b]-2*dis[lca(v,b)] + w;//a->u->b
z = dis[a]+dis[v]-2*dis[lca(a,v)] + dis[u]+dis[b]-2*dis[lca(u,b)] + w;//a->v->b
long long ans = min(x,y);
ans = min(ans,z);
printf("%lld
",ans);
}
}
return 0;
}