HDU_5692_dfs序+线段树

http://acm.hdu.edu.cn/showproblem.php?pid=5692

这道题真的是看了题解还搞了一天，把每条路径后序遍历按1-n重新标号，储存每个点在哪些路径中出现过（l和r数组），然后转化成线段树来更新和取最大值。

注意，如果使用递归建线段树，数组要开4n才能保证不超。

刚开始更新的函数每一遍更新了所有子树，然后超时了，后来在tree中加了个add，保存子树需要增加的量，如果用到这个子树，在把这个量加起来，简直巧妙。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define INF 0x3f3f3f3f

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

vector<int> line[];

int n,m,cnt,l[],r[];

long long w[],init[];

struct segtree

{

    int left,right;

    long long maxx,add;

}tree[];

void dfs(int now,int pre,long long sum)

{

    sum += w[now];

    int flag = ;

    l[now] = INF;

    for(int i = ;i < line[now].size();i++)

    {

        int next = line[now][i];

        if(next == pre) continue;

        flag = ;

        dfs(next,now,sum);

        l[now] = min(l[now],l[next]);

    }

    init[cnt] = sum;

    r[now] = cnt++;

    if(flag)    l[now] = r[now];

}

void build(int pos,int l,int r)

{

    tree[pos].left = l;

    tree[pos].right = r;

    tree[pos].add = ;

    if(l == r)  tree[pos].maxx = init[l];

    else

    {

        int mid = (l+r)/;

        build(pos*,l,mid);

        build(pos*+,mid+,r);

        tree[pos].maxx = max(tree[pos*].maxx,tree[pos*+].maxx);

    }

}

void update(int pos,int l,int r,long long v)

{

    if(tree[pos].add != )

    {

        if(tree[pos].left != tree[pos].right)

        {

            tree[pos*].maxx += tree[pos].add;

            tree[pos*].add += tree[pos].add;

            tree[pos*+].maxx += tree[pos].add;

            tree[pos*+].add += tree[pos].add;

            tree[pos].add = ;

        }

    }

    if(tree[pos].left ==

       l && r == tree[pos].right)

    {

        tree[pos].maxx += v;

        tree[pos].add += v;

        return;

    }

    int mid = (tree[pos].left+tree[pos].right)/;

    if(r <= mid)    update(pos*,l,r,v);

    else if(l > mid)    update(pos*+,l,r,v);

    else

    {

        update(pos*,l,mid,v);

        update(pos*+,mid+,r,v);

    }

    tree[pos].maxx = max(tree[pos*].maxx,tree[pos*+].maxx);

}

long long getmax(int pos,int l,int r)

{

    if(tree[pos].add != )

    {

        if(tree[pos].left != tree[pos].right)

        {

            tree[pos*].maxx += tree[pos].add;

            tree[pos*].add += tree[pos].add;

            tree[pos*+].maxx += tree[pos].add;

            tree[pos*+].add += tree[pos].add;

            tree[pos].add = ;

        }

    }

    if(tree[pos].left == l && r == tree[pos].right) return tree[pos].maxx;

    int mid = (tree[pos].left+tree[pos].right)/;

    if(r <= mid)    return getmax(pos*,l,r);

    if(l > mid)     return getmax(pos*+,l,r);

    return max(getmax(pos*,l,mid),getmax(pos*+,mid+,r));

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int z = ;z <= T;z++)

    {

        printf("Case #%d:\n",z);

        scanf("%d%d",&n,&m);

        for(int i = ;i < n;i++)    line[i].clear();

        for(int i = ;i < n-;i++)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            line[x].push_back(y);

            line[y].push_back(x);

        }

        for(int i = ;i < n;i++)    scanf("%lld",&w[i]);

        cnt = ;

        dfs(,,);

        build(,,n);

        while(m--)

        {

            int op;

            scanf("%d",&op);

            if(op == )

            {

                int x,y;

                scanf("%d%d",&x,&y);

                long long temp = y-w[x];

                w[x] = y;

                update(,l[x],r[x],temp);

            }

            else

            {

                int x;

                scanf("%d",&x);

                printf("%lld\n",getmax(,l[x],r[x]));

            }

        }

    }

    return ;

}

巴特西

HDU_5692_dfs序+线段树

最新文章

热门文章