题意

n个节点的一棵树，每个节点的权值为g，q个询问，树上的节点U-V，求U到V的路径的最大子段和。

题解

先考虑这么一个问题：求区间[L,R]的最大子段和。

q个询问，用线段树可以做到每个询问的时间是O(log n)。

线段树的节点x代表区间[L,R]，我们要存这些值：

• sum: 区间[L,R]的总和
• s: 区间[L,R]的最大子段和
• suml: 最大前缀和
• sumr: 最大后缀和

叶子节点这些值都是g[L]，否则先求出左右孩子的值，然后可以计算出当前节点的值。

再考虑原问题，因为是在树上，我们可以用两次dfs把每个节点放到线段树的区间上，使得每个节点和它最长的儿子在区间上是相邻的，其实就是树链剖分一下。

具体地说（后面的内容最好对着代码看），就是第一次dfs求得每个节点的父亲fa，重儿子son，子树节点总数siz，深度dep。第二次dfs，标记u所在的链的顶标top，在区间的下标rk=++w，以及该下标对应的节点id[w]=u，然后如果有son，则dfs2(son,f)，f是当前的链的顶标，接着对于非重儿子v，dfs2(v,v)，因为非重儿子重新起一条链，顶标是本身。

对于查询u和v，将顶标深度大的点往上翻，直到他们的顶标相同。翻的过程求出这一段路径 和 之前翻的路径 合并成的路径的sum等值，也就是用线段树节点来保存。过程和求线段树的差不多。然后顶标相同后，再将深度大的节点和之前的路径合并一下，最后我们有两个点la，ra代表(u,x)和(x,v)，x是最近公共祖先，注意他们的合并是suml+suml，不明白可以画一下，答案就是max(la.s,ra.s,la.suml+ra.suml)。

代码

#include 
    
     #include 
     
      #include 
      
       #define N 100005#define inf (1LL<<60)#define ll long longusing namespace std;struct edge{    int to,next;}e[N<<1];int head[N],cnt;int n,q,g[N];int dep[N],fa[N],siz[N],son[N];int top[N],rk[N],w,id[N];void add(int u,int v){    e[++cnt]=(edge){v,head[u]};head[u]=cnt;}void dfs1(int u){    siz[u]=1;    for(int i=head[u],v;i;i=e[i].next)if(!dep[v=e[i].to]){        fa[v]=u;        dep[v]=dep[u]+1;        dfs1(v);        siz[u]+=siz[v];        if(siz[son[u]]
       
        >1;    build(lson);build(rson);    pushUp(tr[x], tr[x<<1], tr[x<<1|1]);}node query(int L,int R,int l,int r,int x){    if(L<=l&&r<=R)return tr[x];    int m=l+r>>1;    if(R<=m)return query(L,R,lson);    if(L>m) return query(L,R,rson);    node now;    pushUp(now, query(L,R,lson), query(L,R,rson));    return now;}int main() {    scanf("%d",&n);    for(int i=1,u,v;i