FZU 2277 Change(dfs序+树状数组)

待我称王封你为后i 2021-09-30 13:00 316阅读 0赞

## Problem Description ##

There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.

Initially all the node’s value is 0.

We have q operations. There are two kinds of operations.

1 v x k : a\[v\]+=x , a\[v’\]+=x-k (v’ is child of v) , a\[v’’\]+=x-2\*k (v’’ is child of v’) and so on.

2 v : Output a\[v\] mod 1000000007(10^9 + 7).

## Input ##

First line contains an integer T (1 ≤ T ≤ 3), represents there are T test cases.

In each test case:

The first line contains a number n.

The second line contains n-1 number, p2,p3,…,pn . pi is the father of i.

The third line contains a number q.

Next q lines, each line contains an operation. (“1 v x k” or “2 v”)

1 ≤ n ≤ 3\*10^5

1 ≤ pi < i

1 ≤ q ≤ 3\*10^5

1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7

## Output ##

For each operation 2, outputs the answer.

## Sample Input ##

1 1

1 1 2 1

2 1

2 2

## Sample Output ##

2 1

**题意**

给你1个以1为根节点的树，每个节点初始值为0，有下面两个操作

1 v x k : a\[v\]+=x , a\[v’\]+=x-k (v’ is child of v) , a\[v’’\]+=x-2\*k (v’’ is child of v’) and so on.

2 v : Output a\[v\] mod 1000000007(10^9 + 7).

**题解**

v'为v的子节点

a\[v'\]+=x-(deep\[v'\]-deep\[v\])\*k

a\[v'\]+=x+deep\[v\]\*k-deep\[v'\]\*k

对于x+deep\[v\]\*k可以直接更新\[s\[v\],e\[v\]\]

对于-deep\[v'\]\*k可以维护一个sumk\[v'\]+=k，最后查询的时候\*deep\[v'\]

**代码**

1 #include<cstdio>
     2 #include<vector>
     3 using namespace std;
     4 
     5 const int maxn=3e5+5;
     6 const int mod=1e9+7;
     7 
     8 int s[maxn],e[maxn],deep[maxn],sum[maxn],sumk[maxn],tot,n;
     9 vector<int>G[maxn];
    10 void dfs(int u)
    11 {
    12     s[u]=++tot;
    13     for(vector<int>::iterator v=G[u].begin();v!=G[u].end();v++)
    14         deep[*v]=deep[u]+1,
    15         dfs(*v);
    16     e[u]=tot;
    17 }
    18 void update(int x,int add)
    19 {
    20     for(int i=x;i<=n;i+=(i&-i))sum[i]=(sum[i]+add)%mod;
    21 }
    22 void update1(int x,int add)
    23 {
    24     for(int i=x;i<=n;i+=(i&-i))sumk[i]=(sumk[i]+add)%mod;
    25 }
    26 int query(int x,int y)
    27 {
    28     int ret=0,ans=0;
    29     for(int i=x;i;i-=(i&-i))ret=(ret*1LL+sum[i])%mod;
    30     for(int i=x;i;i-=(i&-i))ans=(ans*1LL+sumk[i])%mod;
    31     ans=ans*1LL*deep[y]%mod;
    32     return (ret+ans)%mod;
    33 }
    34 void init()
    35 {
    36     tot=0;
    37     for(int i=1;i<=n;i++)
    38     {
    39         sum[i]=sumk[i]=0;
    40         G[i].clear();
    41     }
    42 }
    43 int main()
    44 {
    45     int _,u,v,x,op,Q,k;
    46     scanf("%d",&_);
    47     while(_--)
    48     {
    49         init();
    50         scanf("%d",&n);
    51         for(int i=2;i<=n;i++)
    52         {
    53             scanf("%d",&u);
    54             G[u].push_back(i);
    55         }
    56         dfs(1);
    57         scanf("%d",&Q);
    58         for(int i=0;i<Q;i++)
    59         {
    60             scanf("%d",&op);
    61             if(op==1)
    62             {
    63                 scanf("%d%d%d",&v,&x,&k);
    64                 int ret=(x+deep[v]*1LL*k)%mod;
    65                 update(s[v],ret);
    66                 update(e[v]+1,-ret+mod);
    67                 update1(s[v],-k+mod);
    68                 update1(e[v]+1,k);
    69             }
    70             else
    71             {
    72                 scanf("%d",&v);
    73                 printf("%d\n",query(s[v],v));
    74             }
    75         }
    76     }
    77     return 0;
    78 }

转载于:https://www.cnblogs.com/taozi1115402474/p/9657174.html