如果你WA45pts，有可能是答案合并的顺序出错了

错误代码：

int query_chain(int u,int v){
    segment ans1;
    int x = lca(u,v);
    while(top[u] != top[x]){
        ans1 = merge(ans1,query(dfn[top[u]],dfn[u],1,n,1));
        u = father[top[u]];
    }
    ans1 = merge(ans1,query(dfn[x],dfn[u],1,n,1));
    segment ans2;
    while(top[v] != top[x]){
        ans2 = merge(ans2,query(dfn[top[v]],dfn[v],1,n,1));
    }
    ans2 = merge(ans2,query(dfn[x],dfn[v],1,n,1));
    int ans = ans1.val + ans2.val;
    return ans;
}

正确代码：

int query_chain(int u,int v){
    segment ans1;
    int x = lca(u,v);
    while(top[u] != top[x]){
        ans1 = merge(query(dfn[top[u]],dfn[u],1,n,1),ans1);
        u = father[top[u]];
    }
    ans1 = merge(query(dfn[x],dfn[u],1,n,1),ans1);
    segment ans2;
    while(top[v] != top[x]){
        ans2 = merge(query(dfn[top[v]],dfn[v],1,n,1),ans2);
        v = father[top[v]];
    }
    ans2 = merge(query(dfn[x],dfn[v],1,n,1),ans2);
    int ans = ans1.val + ans2.val;
    return ans;
}

因为我们是从下往上跳，所以是合并到前面，而不是后面