absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[搬家]Codeforces 257E (Round 159 Div 2)
[搬家]Codeforces 576B

[搬家]树链剖分.最后一题 BZOJ 4034

absi2011 posted @ Nov 20, 2015 10:49:10 PM in 刷题记录 with tags 树链剖分 线段树 DFS bzoj 原博客 , 446 阅读
希望这题不要变成权限题...
有点害怕= =
算法:树链剖分
数组开小啦RE啦.....
cout被卡出RE啦.....
题目如下:
Description
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:
操作 1 :把某个节点 x 的点权增加 a 。
操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数,表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。
再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操
作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
Output
 对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

 

Sample Output
6
9
13
 

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
struct edge
{
    int y;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
edge * hev_ch[1000005];
int father[100005];
int size[100005];
int up[100005];
void dfs1(int x)
{
    edge * t;
    int max_val=0;
    size[x]=1;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        father[t->y]=x;
        dfs1(t->y);
        size[x]+=size[t->y];
        if (size[t->y]>max_val)
        {
            max_val=size[t->y];
            hev_ch[x]=t;
        }
    }
}
int dfn[100005];
int vis[100005];
void dfs2(int x)
{
    static int now=0;
    dfn[x]=now;
    vis[now]=x;
    now++;
    if (hev_ch[x]==0) return;
    up[hev_ch[x]->y]=up[x];
    dfs2(hev_ch[x]->y);
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        if (t==hev_ch[x]) continue;
        up[t->y]=t->y;
        dfs2(t->y);
    }
}
long long val[1<<18],tag[1<<18];
void push_down(int num,int l,int r)
{
    if (tag[num]==0) return;
    int mid=(l+r)>>1;
    val[num*2+1]+=(mid-l)*tag[num];
    val[num*2+2]+=(r-mid)*tag[num];
    tag[num*2+1]+=tag[num];
    tag[num*2+2]+=tag[num];
    tag[num]=0;
}
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=a[vis[l]];
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    val[num]=val[num*2+1]+val[num*2+2];
}
long long query(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    push_down(num,l,r);
    long long ans=0;
    if (l0<mid) ans+=query(num*2+1,l,mid,l0,r0);
    if (mid<r0) ans+=query(num*2+2,mid,r,l0,r0);
    return ans;
}
void change1(int num,int l,int r,int k,int t)
{
    if (l==r-1)
    {
        val[num]+=t;
        return;
    }
    push_down(num,l,r);
    int mid=(l+r)/2;
    if (k<mid)
    {
        change1(num*2+1,l,mid,k,t);
    }
    else
    {
        change1(num*2+2,mid,r,k,t);
    }
    val[num]=val[num*2+1]+val[num*2+2];
}
void change2(int num,int l,int r,int l0,int r0,int t)
{
    if ((l0<=l)&&(r<=r0))
    {
        val[num]+=(long long)t*(r-l);
        tag[num]+=t;
        return;
    }
    push_down(num,l,r);
    int mid=(l+r)/2;
    if (l0<mid) change2(num*2+1,l,mid,l0,r0,t);
    if (mid<r0) change2(num*2+2,mid,r,l0,r0,t);
    val[num]=val[num*2+1]+val[num*2+2];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    father[0]=-1;
    up[0]=0;
    dfs1(0);
    dfs2(0);
    build_tree(0,0,n);
    for (i=0;i<m;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            change1(0,0,n,dfn[x],y);
        }
        else if (oper==2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            change2(0,0,n,dfn[x],dfn[x]+size[x],y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            x--;
            long long sum=0;
            for (;x!=-1;)
            {
                sum+=query(0,0,n,dfn[up[x]],dfn[x]+1);
                x=father[up[x]];
            }
            cout<<sum<<'\n';
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter