HYSBZ4034-T2

4034: [HAOI2015]樹上操作

Time Limit: 10 Sec   Memory Limit: 256 MB

Submit: 5552   Solved: 1783

[ Submit][ Status][ Discuss]

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

HINT

 對于 100% 的資料， N,M<=100000 ，且所有輸入資料的絕對值都不會超過 10^6 。

Source

鳴謝bhiaibogf提供

解題思路：樹鍊剖分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>
#include <set>
#include <vector>
#include <functional>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

int n,m,x,y,z;
int s[200009],nt[200009],e[200009],cnt;
int ct[200009],mx[200009],fa[200009],dep[200009];
int top[200009],L[200009],R[200009],g[200009],a[200009];
LL sum[200009<<2],lazy[200009<<2];

void dfs(int x,int f)
{
    dep[x]=dep[f]+1;
    fa[x]=f;ct[x]=1,mx[x]=0;
    for(int i=s[x];~i;i=nt[i])
    {
        if(e[i]==f) continue;
        dfs(e[i],x);
        ct[x]+=ct[e[i]];
        if(ct[e[i]]>ct[mx[x]]) mx[x]=e[i];
    }
}

void Dfs(int x,int t)
{
    top[x]=!t?x:top[fa[x]];
    L[x]=++cnt;g[cnt]=x;
    if(mx[x]) Dfs(mx[x],1);
    for(int i=s[x];~i;i=nt[i])
    {
        if(e[i]==fa[x]||e[i]==mx[x]) continue;
        Dfs(e[i],0);
    }
    R[x]=cnt;
}

void build(int k,int l,int r)
{
    lazy[k]=0;
    if(l==r) {sum[k]=a[g[l]];return ;}
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}

LL query(int k,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr) return sum[k];
    int mid=(l+r)>>1;
    if(lazy[k])
    {
        lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
        sum[k<<1]+=lazy[k]*(mid-l+1),sum[k<<1|1]+=lazy[k]*(r-mid);
        lazy[k]=0;
    }
    LL ans=0;
    if(ll<=mid) ans+=query(k<<1,l,mid,ll,rr);
    if(rr>mid) ans+=query(k<<1|1,mid+1,r,ll,rr);
    return ans;
}

void update(int k,int l,int r,int ll,int rr,int val)
{
    if(l>=ll&&r<=rr) {sum[k]+=1LL*val*(r-l+1);lazy[k]+=val;return ;}
    int mid=(l+r)>>1;
    if(lazy[k])
    {
        lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
        sum[k<<1]+=lazy[k]*(mid-l+1),sum[k<<1|1]+=lazy[k]*(r-mid);
        lazy[k]=0;
    }
    if(ll<=mid) update(k<<1,l,mid,ll,rr,val);
    if(rr>mid) update(k<<1|1,mid+1,r,ll,rr,val);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}

LL getans(int x,int y)
{
    LL ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=query(1,1,n,L[top[x]],L[x]);x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return ans+query(1,1,n,L[x],L[y]);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(s,-1,sizeof s);
        ct[0]=dep[0]=cnt=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            nt[cnt]=s[x],s[x]=cnt,e[cnt++]=y;
            nt[cnt]=s[y],s[y]=cnt,e[cnt++]=x;
        }
        dfs(1,0);
        Dfs(1,cnt=0);
        build(1,1,n);
        while(m--)
        {
            scanf("%d",&x);
            if(x==3)
            {
                scanf("%d",&y);
                printf("%lld\n",getans(1,y));
            }
            else
            {
                scanf("%d%d",&y,&z);
                update(1,1,n,L[y],x==1?L[y]:R[y],z);
            }
        }
    }
    return 0;
}