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

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#define ll long longusing 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;vectorG[maxn];void dfs(int u,int fa,int d)//记录深度和父亲{ deep[u]=d; p[u][0]=fa; for(int i=0;i=0;j--) { if(deep[a]-(1<=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;ib;}int main(){ memset(p,-1,sizeof(p)); scanf("%d",&n); int u,v; for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。