3631. Delivery Service（倍增lca+树上差分）

EOJ Delivery Service Company handles a massive amount of orders in our nation. As is well known, our nation has n cities, with n−1 bi-directional paths connecting them, forming a tree. The length of the i-th path is wi, meaning that the time we have to spend walking through this path is wi.

Now, you, as the headquarter of EOJ, has somehow learned a magic spell. Each time you cast a spell on two paths, the lengths of these two paths magically swap with each other. You can do this magic as many times as you want (possibly none).

We have q orders waiting to be handled. The i-th order demands sending a package from city si to city ti. We kindly ask you to do your magic before all the deliveries start, such that the total time we have to spend on delivering these packages is minimized.

Input

The first line of the input contains one single integer n (1≤n≤2⋅105).

The next n−1 lines tell about the path information from path 1 to path n−1, the i-th of which contains three space-separated integers ui, vi and wi (1≤ui,vi≤n, ui≠vi, 1≤wi≤1000).

The next line contains one integer q (1≤q≤2⋅105).

The next q lines each contains two space-separated integers si and ti (1≤si,ti≤n,si≠ti).

Output

Output one integer, the minimum total time you can achieve.

Examples

input

5

1 2 2

1 3 3

3 4 3

3 5 4

2

1 5

4 2

output

14

题目大概：

给出一颗树，树的边上有边权。然后q次询问，每次询问 u v的最短距离，在询问前，可以用魔法来换任意两个边，可以使用任意次魔法，问所有询问的最小值是多少。

思路：

可以使用任意次魔法，就是可以交换任意边，那么一定把用的最多次数的边变成最小的，以此类推。

需要在树上标记路径覆盖次数，可以用树上差分+lca来实现。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+100;
const int mod=1e9+7;
const int INF=1e9+7;
int deep[maxn];
int w[maxn],p[maxn][30];
int use[maxn];
int n,q;
vector<int>G[maxn];

void dfs(int u,int fa,int d)//记录深度和父亲
{
    deep[u]=d;
    p[u][0]=fa;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa)continue;
        dfs(v,u,d+1);
    }
}
void getp()//计算出p数组
{           //p[i][j]  i节点的第2^j祖先是谁
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++){
            if(p[i][j-1]==-1)continue;
                p[i][j]=p[p[i][j-1]][j-1];
        }
}
int lca(int a,int b)//求出a和b的lca
{
    int i,j;
    if(deep[a]<deep[b])swap(a,b);
    for(i=0;(1<<i)<=deep[a];i++);
    i--;
    for(j=i;j>=0;j--)
    {
        if(deep[a]-(1<<j)>=deep[b])
        a=p[a][j];
    }
    if(a==b)return a;
    for(j=i;j>=0;j--)
    {
        if(p[a][j]!=-1&&p[a][j]!=p[b][j])
        {
            a=p[a][j];
            b=p[b][j];
        }
    }
    return p[a][0];
}

int dfs2(int u,int fa)  //计算出所有边的覆盖次数
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa)continue;
        dfs2(v,u);
        use[u]+=use[v];
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    memset(p,-1,sizeof(p));
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w[i]);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    sort(w+1,w+n);
    dfs(1,1,0);
    getp();
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&u,&v);
        int lc=lca(u,v);
        use[lc]-=2;
        use[u]++;
        use[v]++;
    }
    dfs2(1,1);
    sort(use+1,use+1+n,cmp);
    ll sum=0;
    for(int i=1;i<n;i++)
    {
        sum+=use[i]*w[i];
    }
    printf("%lld\n",sum);
    return 0;
}