hiho 1995 树上的最短边

https://hihocoder.com/problemset/problem/1995

题目

给定一棵包含N个节点的带权树，节点编号1~N。小Hi每次会给定树上两个节点的编号u和v，请你计算从u到v的路径上，哪条边的权值最小。

请你输出最小的权值。

思路

显然是个lca，倍增lca的时候加个维护边权就可以了。但是我拒绝
脑子抽筋想写个点分治，点分治做起来也很简单，先把询问离线，重心合并的时候就看某次询问在不在重心划分出的不同子树上，是的话遍历时候更新一下就好了。时间复杂度O(nlogn)

代码

#include
using namespace std;
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MEM(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll mod = 1e9+7;
const int maxn =1e6+10;
ll n,k;
int N,K;
int root,Max;
struct node{
    int v,next,w;
}edge[maxn*2];

int head[maxn],tot,num1,num2;
int si[maxn],maxv[maxn],vis[maxn];//vis标记重心

vector> E[maxn];
int cnt[maxn];
int ans[maxn];
const int inf =1e9+7;


void init(){
    tot=0;MEM(head,-1);MEM(vis,0);
}
void add_edge(int u,int v,int w){
    edge[tot].v=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;
}
//处理子树的大小（固定）
void dfssi(int u,int f){
    si[u]=1;
    maxv[u]=0;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==f||vis[v])continue;
        dfssi(v,u);
        si[u]+=si[v];
        if(si[v]>maxv[u])maxv[u]=si[v];
    }
}
//找重心（固定）
void dfsroot(int r,int u,int f){
    if(si[r]-si[u]>maxv[u])//si[r]-si[u]是u上面部分的树的尺寸，跟u的最大孩子比，找到最大孩子的最小差值节点
        maxv[u]=si[r]-si[u];
    if(maxv[u]