Gym101889 - I Imperial roads（最小生成树，树链剖分）

链接：Gym101889

题意：

给出$R$条带权边，构建一棵$N(2\le N\le 10^5)$个结点的最小生成树，共$Q(1\le Q\le 10^5)$次询问，每次询问必选边$(U,V)$的最小生成树的边权和。

分析:

先不考虑必选边，建一棵最小生成树，对于询问必选边$(U,V)$，找到最小生成树中$U$,$V$路径上最大边权，然后删除该边，将边$(U,V)$加上即可。

对于找到树上$U$,$V$路径上的最大边权，将 边权 赋到 该边更深结点 的 点权上，然后用树链剖分即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int maxn=1e6+10;
int N,R,Q,min_sum=0;
struct road
{
    int u;int v;