A. 昔我往矣

  题目要求我们求取最小的翻新代价。每条边只有在第一次走过的时候才会被翻新，即增加翻新的代价。如果我们直接使用最短路算法的话，需要判断当前最短路上的路径是否被翻新过，也就是说我们是需要回溯最短路径，将沿路的翻新费用更新为0。因此需要对\(5\)个点的两两组合进行判断，实现起来还是比较麻烦的。
  一个更加容易实现的算法是利用\(lca\)，我们先找到\(5\)个点中\(dfs\)序最大和最小的两个点，计算一下它们之间的距离。然后将余下的三个节点合并到这条路径上。具体的做法是在选择一个点\(v\)加入时，找到该节点与已加入节点间\(lca\)最深的点，这就是已合并路径的一条子链，我们只要加入到结果当中去就可以了。

#include<bits/stdc++.h>

using namespace std;

const int N=5e4+10;
const int M=N<<1;

int h[N],e[M],ne[M],w[M],idx;
int dfn[N],tot;
int dis[N];
int fa[25][N];
int node[10];
int dep[N];

void add(int a,int b,int c)
{
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//计算dfs序
void dfs(int x)
{
    dfn[x]=++tot;//当前节点的dfs序
    dep[x]=dep[fa[0][x]]+1;

    for(int i=h[x];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa[0][x]) continue;
        fa[0][v]=x;
        dis[v]=dis[x]+w[i];
        for(int j=1;j<25;j++)
        {
            fa[j][v]=fa[j-1][fa[j-1][v]];
        }
        dfs(v);
    }
    return;
}

int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=24;i>=0;i--)
    {
        if(dep[fa[i][x]]>=dep[y])
            x=fa[i][x];
    }
    if(x==y) return x;//y是最近公共祖先
    for(int i=24;i>=0;i--)
    {
        if(fa[i][x]!=fa[i][y])
        {
            x=fa[i][x];
            y=fa[i][y];
        }
    }
    return fa[0][x];
}

bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}

int main()
{
    int n;
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(0);
    dis[0]=0;
    int q;
    scanf("%d",&q);
    while(q--)
    {
        for(int i=0;i<5;i++) scanf("%d",&node[i]);
        sort(node,node+5,cmp);
        int father=lca(node[0],node[4]);
        int res=dis[node[0]]+dis[node[4]]-2*dis[father];
        swap(node[1],node[4]);

        for(int i=2;i<5;i++)
        {
            int dep_lca=0;
            for(int j=0;j<i;j++)
            {
                int cur_lca=lca(node[i],node[j]);
                if(!dep_lca||dep[cur_lca]>dep[dep_lca])
                    dep_lca=cur_lca;
            }
            res+=dis[node[i]]-dis[dep_lca];
        }
        printf("%d\n",res);
    }

    return 0;
}