HDU 5052(ツリーチェーン分割+セグメントツリー)

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5052
标题:木の上の各点には商品の価格に対応する重みがあり、毎回2点の間の経路を調べ、XからYまで歩いて、ある点で商品を購入して別の点で商品を売る(販売点は必ず購入点の後ろにある)ことを選択することができ、この経路を通るたびに、この経路上のすべての点の商品の価格はV上昇する.各クエリについて、Yまでの最大利益を求める(0以上、購入しないことを選択).
分析:この問題はPOJ 3728(リンク:http://poj.org/problem?id=3728)は非常に似ていますが、POJの問題は点更新の操作がないので、オフライン後に帯権で調べてセットして答えを調べることができます.しかし、この問題は通るたびにチェーン全体の点を更新する必要があるので、オフラインは絶対にだめです.しかし、同じようにその問題の考え方に倣って、セグメントツリーで対応する値を維持することができます.
まず,線形の一次元配列であれば,XからYの最大収益を求めることが線分木の区間合併問題であると考える.各区間ごとに最大値、最小値、現在の区間の答えを維持し、区間を合併する際に左右のサブ区間の答えへの貢献をそれぞれ考慮し、最小値が左の最大値が右の場合、合併後の区間の答えである.1次元配列の線形状況の問題を解決した後,ツリー上の状況を考慮した. 
XからYへ行くと答えを3つに分けることができ、XとYの最近の公共祖先をLCAとする.
1.XからLCAまでの道で購入・販売
2.LCAからYへの道で購入・販売
3..X~LCAで購入し、LCA~Yで販売
一次元配列とは異なり、LCAからYまで木で切ると題意とは逆なので、下から上へ行く答えだけでなく、上から下へ行く答えも維持する必要があります.次に、新しいクエリの答えを前のものとマージします.XとYが同じ重鎖に到達した場合,XとYの上下関係を状況別に検討すると,合併方式に少し違いがある.
ツリー上のポイント権更新は、区間更新であるため、区間全体が更新されると、区間の最大値と最小値にのみ影響し、答えはまったく影響を受けないため、lazy操作を使用してクエリーまたは更新時にドロップします.
昨日HDU 4718を书いて长い间、今日1 Aはとても楽しいです
コード:

#include 
#include 
#include 
#include 
#define ld d<<1
#define rd d<<1|1
#define lson ld,l,m
#define rson rd,m+1,r
using namespace std;
const int N = 50000 +5;
int n,m;
vectorg[N];
int val[N];
int dfn[N],rnk[N],dep[N],fa[N],son[N],siz[N],top[N];
int tot;
void dfs1(int u,int f,int d)
{
    fa[u] = f;
    son[u] = -1;
    siz[u] = 1;
    dep[u] = d;
    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if(v == f) continue;
        dfs1(v,u,d+1);
        siz[u] += siz[v];
        if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
    }
    return;
}
void dfs2(int u,int t)
{
    dfn[u] = tot;
    rnk[tot++] = u;
    top[u] = t;
    if(son[u] == -1) return;
    dfs2(son[u],t);
    for(int i = 0; i > 1;
    build(lson);
    build(rson);
    tr[d] = merge(tr[ld],tr[rd]);
    return;
}
node query(int d,int l,int r,int ql,int qr)
{
    if(ql <= l && r<= qr)
    {
        return tr[d];
    }
    int m = (l + r) >> 1;
    pushdown(d);
    node ans1 = node(), ans2 = node();
    if(m < ql) return query(rson,ql,qr);
    if(qr <= m) return query(lson,ql,qr);
     ans1 = query(lson,ql,qr); ans2 = query(rson,ql,qr);
    return merge(ans1,ans2);
}
void update(int d,int l,int r,int ql,int qr,int v)
{
    if(ql <= l && r <= qr)
    {
        tr[d].minn += v;
        tr[d].maxx += v;
        tr[d].lz += v;
        return;
    }
    int m = (l+r) >> 1;
    pushdown(d);
    if(ql <= m) update(lson,ql,qr,v);
    if(m  dep[fy])
        {
            if(fl1 == 0)
            {
                ans1 = query(1,1,n,dfn[fx],dfn[x]);
                fl1 = 1;
            }
            else ans1 = merge(query(1,1,n,dfn[fx],dfn[x]),ans1);
            update(1,1,n,dfn[fx],dfn[x],v);
            x = fa[fx], fx = top[x];
        }
        else
        {
            if(fl2 == 0)
            {
                ans2 = query(1,1,n,dfn[fy],dfn[y]);
                fl2 = 1;
            }
            else ans2 = merge(query(1,1,n,dfn[fy],dfn[y]),ans2);
            update(1,1,n,dfn[fy],dfn[y],v);
            y = fa[fy], fy = top[y];
        }
    }
    int res = 0;
    if(dep[x] <= dep[y])
    {
        node ans3 = query(1,1,n,dfn[x],dfn[y]);
        res = ans3.downans;
        if(fl2 != 0)
        {
            ans3 = merge(ans3,ans2);
            res = max(res,ans3.downans);
        }
        if(fl1 != 0)
        {
           res = max(res,max(ans1.upans,ans3.downans));
           res = max(res,ans3.maxx - ans1.minn);
        }
        update(1,1,n,dfn[x],dfn[y],v);
    }
    else
    {
        node ans3 = query(1,1,n,dfn[y],dfn[x]);
        if(fl1 != 0) ans3 = merge(ans3,ans1);
        res = ans3.upans;
        if(fl2 != 0)
        {
            res =max(res,max(ans3.upans,ans2.downans));
            res = max(res,ans2.maxx - ans3.minn);
        }
        update(1,1,n,dfn[y],dfn[x],v);
    }
    return res;
}
int main()
{
    int times; scanf("%d",&times);
    while(times --)
    {
        scanf("%d",&n); tot =1;
        for(int i = 1; i <= n; i++) scanf("%d",&val[i]),g[i].clear();
        for(int i = 1; i < n; i++)
        {
            int u,v; scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        scanf("%d",&m);
        for(int i = 0; i < m; i++)
        {
            int x,y,z; scanf("%d%d%d",&x,&y,&z);
            printf("%d
",solve(x,y,z));
        }
    }
    return 0;
}