树剖模板题啊！

这道题的话，最通（jian）俗（dan）易（cu）懂（bao）的解法应该就是树剖了。

加上线段树维护树上路径的最大权值（\(Max\)）和路径和（\(sum\)）。

至于\(LCT\)这种高级操作对于我这种新手还是比较困难的\(qwq\)

以下是参考代码：（有什么问题欢迎指教！）

#include
    
     const int MAXN=30010;inline int max(int a,int b){return a>b?a:b;}inline int read(){    int s=0;bool f=false;char c=getchar();    while(c<'0'||c>'9')f|=(c=='-'),c=getchar();    while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();    return (f)?(-s):(s);}int n,m,summ,maxx;int seg[MAXN],rev[MAXN],top[MAXN];int dep[MAXN],siz[MAXN],son[MAXN],father[MAXN];int tot,ver[MAXN<<1],fir[MAXN<<1],nxt[MAXN<<1];inline void Add_edge(int u,int v){    nxt[++tot]=fir[u],fir[u]=tot,ver[tot]=v;    nxt[++tot]=fir[v],fir[v]=tot,ver[tot]=u;}int val[MAXN],sum[MAXN<<2],Max[MAXN<<2];inline int lc(int rt){return rt<<1;}inline int rc(int rt){return rt<<1|1;}inline void push_sum(int rt){    sum[rt]=sum[lc(rt)]+sum[rc(rt)];}inline void push_max(int rt){    Max[rt]=max(Max[lc(rt)],Max[rc(rt)]);}inline void build(int rt,int l,int r){    if(l==r)        sum[rt]=Max[rt]=val[rev[l]];    else{        int mid=(l+r)>>1;        build(lc(rt),l,mid);        build(rc(rt),mid+1,r);        push_sum(rt),push_max(rt);    }}inline void update(int rt,int l,int r,int id,int v){    if(id
     
      r) return;    if(l==r&&l==id)        sum[rt]=Max[rt]=v;    else{        int mid=(l+r)>>1;        update(lc(rt),l,mid,id,v);        update(rc(rt),mid+1,r,id,v);        push_sum(rt),push_max(rt);    }}inline void query(int rt,int l,int r,int x,int y){    if(r
      
       y) return;    if(x<=l&&r<=y)        summ+=sum[rt],maxx=max(maxx,Max[rt]);    else{        int mid=(l+r)>>1;        query(lc(rt),l,mid,x,y);        query(rc(rt),mid+1,r,x,y);    }}inline void dfs1(int u,int f){    dep[u]=dep[f]+1,siz[u]=1,father[u]=f;    for(int v,i=fir[u];i;i=nxt[i])        if((v=ver[i])!=f){            dfs1(v,u),siz[u]+=siz[v];            if(siz[son[u]]
       
        =dep[fy]){            query(1,1,n,seg[fx],seg[x]);            x=father[fx],fx=top[x];        }        else{            query(1,1,n,seg[fy],seg[y]);            y=father[fy],fy=top[y];        }    }    if(dep[x]<=dep[y])        query(1,1,n,seg[x],seg[y]);    else        query(1,1,n,seg[y],seg[x]);}int main(){    n=read();    for(int i=1;i