1. 首页
2. 线段树
3. 本页

HDU 5692 Snacks (欧拉序列+线段树)

题目链接：点我~~

先dfs求出欧拉序列，就是dfs遍历的顺序，然后更新是更新区间加一个数，查询是查询区间的最大值，即l[x]到r[x]间的最大值，l[x]表示第一次遍历到x点,r[x]表示遍历完有关x节点时的值，区间内就表示有关x的所有值~

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<fstream>
using namespace std;
typedef long long LL;
const LL INF = 1e18 + 7;
const int N = 200100;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

vector<int> mp[N];
int cnt[N];
int val[N];
int l[N], r[N];
int tol;
LL msum[N << 2], sval[N], col[N << 2];

void dfs(int u, int fa)
{
    cnt[++tol] = u;
    l[u] = tol;
    for (int i = 0; i < mp[u].size(); ++i)
    {
        int v = mp[u][i];
        if (v == fa)
        {
            continue;
        }
        sval[v] += sval[u];
        dfs(v, u);
    }
    r[u] = tol;
}

inline void pushup(int rt)
{
    msum[rt] = max(msum[rt << 1], msum[rt << 1 | 1]);
}

void pushdown(int rt)
{
    if (col[rt])
    {
        col[rt << 1] += col[rt];
        col[rt << 1 | 1] += col[rt];
        msum[rt << 1] += col[rt];
        msum[rt << 1 | 1] += col[rt];
        col[rt] = 0;
    }
}

void build(int l, int r, int rt)
{
    msum[rt] = 0;
    col[rt] = 0;
    if (l == r)
    {
        msum[rt] = sval[cnt[l]];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}

void modify(int l, int r, int rt, int tl, int tr, int res)
{
    if (tl <= l && r <= tr)
    {
        msum[rt] += res;
        col[rt] += res;
        return;
    }
    pushdown(rt);
    int m = (l + r) >> 1;
    if (tl <= m)
    {
        modify(lson, tl, tr, res);
    }
    if (tr > m)
    {
        modify(rson, tl, tr, res);
    }
    pushup(rt);
}

LL query(int l, int r, int rt, int tl, int tr)
{
    if (tl <= l && r <= tr)
    {
        return msum[rt];
    }
    pushdown(rt);
    int m = (l + r) >> 1;
    LL res= -INF;
    if (tl <= m)
    {
        res=max(res,query(lson, tl, tr));
    }
    if (tr > m)
    {
        res=max(res,query(rson, tl, tr));
    }
    return res;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t;
    int casee = 1;
    cin >> t;
    int n, m;
    while (t--)
    {
        cin>>n>>m;
        for (int i = 1; i <= n; ++i)
        {
            mp[i].clear();
        }
        int u, v;
        for (int i = 1; i < n; ++i)
        {
            scanf("%d%d", &u, &v);
            u++, v++;
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &val[i]);
            sval[i] = val[i];
        }
        tol = 0;
        dfs(1, 0);
        //cout<<tol<<endl;
        build(1, n, 1);
        printf("Case #%d:\n", casee++);
        int op, x, y;
        while (m--)
        {
            scanf("%d", &op);
            if (op == 0)
            {
                scanf("%d%d", &x, &y);
                x++;
                modify(1, n, 1, l[x], r[x], y-val[x]);
                val[x] = y;
            }
            else
            {
                scanf("%d", &x);
                x++;
                cout << query(1, n, 1, l[x], r[x]) << endl;
            }
        }

    }

    return 0;
}