BZOJ3589: 动态树

3589: 动态树

Time Limit: 30 Sec  Memory Limit: 1024 MB
Submit: 174  Solved: 79
[Submit][Status]

Description

　　小明在楼下种了一棵动态树, 该树每天会在某些节点上长出一些果子. 这棵树的根节点为1, 它有n个节点, n-1条边.

　　别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件

　　事件0:
　　这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个果子.

　　事件1:
　　小明希望你求出几条树枝上的果子数. 一条树枝其实就是一个从某个节点到根的路径的一段. 每次小明会选定一些树枝, 让你求出在这些树枝上的节点的果子数的和. 注意, 树枝之间可能会重合, 这时重合的部分的节点的果子只要算一次.

　　初始时, 每个节点上都没有果子.

Input

　　第一行一个整数n(1<=n<=200,000), 即节点数.
　　接下来n-1行, 每行两个数字u, v. 表示果子u和果子v之间有一条直接的边. 节点从1开始编号.
　　在接下来一个整数nQ(1<=nQ<=200,000), 表示事件.
　　最后nQ行, 每行开头要么是0, 要么是1.
　　如果是0, 表示这个事件是事件0. 这行接下来的2个整数u, delta表示以u为根的子树中的每个节点长出了delta个果子.
　　如果是1, 表示这个事件是事件1. 这行接下来一个整数K(1<=K<=5), 表示这次询问涉及K个树枝. 接下来K对整数u_k, v_k, 每个树枝从节点u_k到节点v_k. 由于果子数可能非常多, 请输出这个数模2^31的结果.

Output

　　对于每个事件1, 输出询问的果子数.

Sample Input

5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4

Sample Output

13

HINT

 1 <= n <= 200,000, 1 <= nQ <= 200,000, K = 5.

生成每个树枝的过程是这样的:先在树中随机找一个节点, 然后在这个节点到根的路径上随机选一个节点, 这两个节点就作为树枝的两端.

Source

By 佚名提供

题解：
各种逗逼。。。
一个暴力的思路是我们每次沿边走然后打上标记，最后输出有标记的点的和。这样是可以过的。
然后我写完之后狂WA不止。。。
对排了几组发现两个标记下传的顺序搞反了。。。T_T
代码：

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<string>

#define inf 1000000000

#define maxn 250000+5

#define maxm 500+100

#define eps 1e-10

#define ll long long

#define pa pair<int,int>

#define for0(i,n) for(int i=0;i<=(n);i++)

#define for1(i,n) for(int i=1;i<=(n);i++)

#define for2(i,x,y) for(int i=(x);i<=(y);i++)

#define for3(i,x,y) for(int i=(x);i>=(y);i--)

#define mod 1000000007

using namespace std;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}

    return x*f;

}
int n,m,q,tot,head[maxn],a[10],b[10],top[maxn],id[maxn][2],son[maxn],dep[maxn],s[maxn],fa[maxn];
struct edge{int go,next;}e[2*maxn];
struct seg{int l,r,tag[2],sum,ret;}t[4*maxn];
inline void insert(int x,int y)
{
    e[++tot]=(edge){y,head[x]};head[x]=tot;
    e[++tot]=(edge){x,head[y]};head[y]=tot;
}
inline void dfs(int x)
{
    s[x]=1;
    for(int i=head[x],y;i;i=e[i].next)
        if(!dep[y=e[i].go])
        {
            dep[y]=dep[x]+1;fa[y]=x;
            dfs(y);
            s[x]+=s[y];
            if(s[y]>s[son[x]])son[x]=y;
        }
}
inline void dfs2(int x,int chain)
{
    id[x][0]=++m;top[x]=chain;
    if(son[x])dfs2(son[x],chain);
    for(int i=head[x];i;i=e[i].next)if(e[i].go!=son[x]&&e[i].go!=fa[x])dfs2(e[i].go,e[i].go);
    id[x][1]=m;
}
inline void pushup(int k)
{
    t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
    t[k].ret=t[k<<1].ret+t[k<<1|1].ret;
    //cout<<k<<' '<<t[k].sum<<' '<<t[k].ret<<endl;
}
inline void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;int mid=(l+r)>>1;t[k].tag[0]=-1;
    if(l==r)return;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
inline void same(int k,int z)
{
    t[k].tag[0]=z;t[k].ret=z==1?t[k].sum:0;
}
inline void update(int k,int z)
{
    t[k].tag[1]+=z;t[k].sum+=(t[k].r-t[k].l+1)*z;
}
inline void pushdown(int k)
{
    if(t[k].tag[1]){update(k<<1,t[k].tag[1]);update(k<<1|1,t[k].tag[1]);t[k].tag[1]=0;}
    if(t[k].tag[0]!=-1){same(k<<1,t[k].tag[0]);same(k<<1|1,t[k].tag[0]);t[k].tag[0]=-1;}
}
inline void change(int k,int x,int y,int z)
{
    if(t[k].tag[0]==z)return;
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==x&&r==y){same(k,z);return;}
    pushdown(k);
    if(y<=mid)change(k<<1,x,y,z);
    else if(x>mid)change(k<<1|1,x,y,z);
    else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z);
    pushup(k);
}
inline void add(int k,int x,int y,int z)
{
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==x&&r==y){update(k,z);return;}
    pushdown(k);
    if(y<=mid)add(k<<1,x,y,z);
    else if(x>mid)add(k<<1|1,x,y,z);
    else add(k<<1,x,mid,z),add(k<<1|1,mid+1,y,z);
    pushup(k);
}
inline void solve(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change(1,id[top[x]][0],id[x][0],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,id[x][0],id[y][0],z);
}

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    n=read();
    for1(i,n-1)insert(read(),read());
    dep[1]=1;dfs(1);dfs2(1,1);
    build(1,1,n);
    q=read();
    while(q--)
    {
        int ch=read();m=read();
        if(!ch)add(1,id[m][0],id[m][1],read());
        else 
        {
            for1(i,m)a[i]=read(),b[i]=read();
            for1(i,m)solve(a[i],b[i],1);
            printf("%d
",t[1].ret&2147483647);
            for1(i,m)solve(a[i],b[i],0);
        }
    }

    return 0;

}