2014微软编程之美初赛第一场第二题 树

描述

有一个N个节点的树，其中点1是根。初始点权值都是0。

一个节点的深度定义为其父节点的深度+1,。特别的，根节点的深度定义为1。

现在需要支持一系列以下操作：给节点u的子树中，深度在l和r之间的节点的权值（这里的深度依然从整个树的根节点开始计算），都加上一个数delta。

问完成所有操作后，各节点的权值是多少。

为了减少巨大输出带来的开销，假设完成所有操作后，各节点的权值是answer[1..N]，请你按照如下方式计算出一个Hash值（请选择合适的数据类型，注意避免溢出的情况）。最终只需要输出这个Hash值即可。

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

   Hash = (Hash * MAGIC + answer[i]) mod MOD;

EndFor

输入

第一行一个整数T (1 ≤ T ≤ 5)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

第一行一个整数N (1 ≤ N ≤ 105)，表示树的节点总数。

接下来N - 1行，每行1个数，a (1 ≤ a ≤ N)，依次表示2..N节点的父亲节点的编号。

接下来一个整数Q(1 ≤ Q ≤ 105)，表示操作总数。

接下来Q行，每行4个整数，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109)，代表一次操作。

输出

对每组数据，先输出一行“Case x: ”，x表示是第几组数据，然后接这组数据答案的Hash值。

数据范围

小数据：1 ≤ N, Q ≤ 1000

大数据：1 ≤ N, Q ≤ 105

样例解释

点1的子树中有1,2,3三个节点。其中深度在2-3之间的是点2和点3。

点2的子树中有2,3两个节点。其中没有深度为1的节点。

所以，执行完所有操作之后，只有2,3两点的权值增加了1。即答案是0 1 1。再计算对应的Hash值即可。

样例输入

1
3
1
2
2
1 2 3 1
2 1 1 1

样例输出

Case 1: 12348

这道题当时纯模拟大数据的时候果断TLE了，后来参考了大神的博客，用树状态数组+dfs做的

用h[]数组记录深度，用num[]数组存某个深度下的权值，一边dfs，一边更新num数组。但是值得注意的是某个点的权值就是他那个深度上的权值.但是加权操作时不是一整层都加的，只是加某一子树上的，如果给一整层都加上，会影响到别的不该加权的子树，这怎么办呢？别急，算完这颗子树，再把加权都减掉就好了。这里巧在计算的顺序，不是一口气算出所有点权，都是按照dfs序一个个算。按dfs序，遍历到某点，执行u等于该点区间操作，更新之前建的线段树。由于与他祖先节点相关的操作都已经更新到线段树上了，所以当前线段树上对应深度的值就是他的权值。等遍历出了他这棵子树，也就是他的孩子节点都算完了，再把之间的操作消掉。挺巧妙的一个思路。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
const long long M=1000000007;
const int MAX=100005;
long long num[MAX];
int h[MAX];
vector<int> L[MAX],R[MAX],del[MAX],G[MAX];
int N;
class BIT
{
private:
    long long bit[MAX];
    int lowbit(int i)
    {
        return i&-i;
    }
public:
    void Clear()
    {
        memset(bit,0,sizeof(bit));
    }
    void update(int i,int v)
    {
        v%=M;
        while(i<=N)
        {
            bit[i]+=v;
            bit[i]%=M;
            i+=lowbit(i);
        }
    }
    long long getsum(int i)
    {
        long long s=0;
        while(i>0)
        {
            s+=bit[i];
            s%=M;
            i-=lowbit(i);
        }
        return s;
    }
};
BIT tree;
long long cal()
{
    long long ans=0;
    for(int i=1;i<=N;i++)
    {
        ans=(ans*12347+num[i])%M;
    }
    return ans;
}

void dfs(int u,int depth)
{
    h[u]=depth;
    for(int i=0;i<L[u].size();i++)
    {
        tree.update(L[u][i],del[u][i]);
        tree.update(R[u][i]+1,-del[u][i]);
    }
    num[u]=tree.getsum(h[u]);
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        dfs(v,depth+1);
    }
    for(int i=0;i<L[u].size();i++)
    {
        tree.update(L[u][i],-del[u][i]);
        tree.update(R[u][i+1],del[u][i]);
    }
}
int main()
{
    int T;
    while(scanf("%d",&T)!=EOF)
    {
        for(int kase=1;kase<=T;kase++)
        {
            tree.Clear();
            scanf("%d",&N);
            for(int i=1;i<=N;i++)
            {
                L[i].clear();
                R[i].clear();
                del[i].clear();
                G[i].clear();
            }
            for(int i=2;i<=N;i++)
            {
                int fa;
                scanf("%d",&fa);
                G[fa].push_back(i);
            }
            int Q,u,l,r,d;
            scanf("%d",&Q);
            while(Q--)
            {
                scanf("%d%d%d%d",&u,&l,&r,&d);
                L[u].push_back(l);
                R[u].push_back(r);
                del[u].push_back(d);
            }
            dfs(1,1);
            printf("Case %d: %lld\n",kase,cal());
        }
    }
    return 0;
}

2014微软编程之美初赛第一场第二题 树,布布扣,bubuko.com

2014微软编程之美初赛第一场第二题 树

原文：http://blog.csdn.net/asdfghjkl1993/article/details/24306921