bzoj4034

http://www.lydsy.com/JudgeOnline/problem.php?id=4034

树链剖分。

跟NOI2015的“软件包管理”一模一样。。。。。

河南的爽死了。。。。。。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<fstream>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<utility>

#include<set>

#include<bitset>

#include<vector>

#include<functional>

#include<deque>

#include<cctype>

#include<climits>

#include<complex>

//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj

using namespace std;

typedef long long LL;

typedef double DB;

typedef pair<int,int> PII;

typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))

#define mmcy(a,b) memcpy(a,b,sizeof(a))

#define fill(a,l,r,v) fill(a+l,a+r+1,v)

#define re(i,a,b)  for(i=(a);i<=(b);i++)

#define red(i,a,b) for(i=(a);i>=(b);i--)

#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)

#define fi first

#define se second

#define m_p(a,b) make_pair(a,b)

#define SF scanf

#define PF printf

#define two(k) (1<<(k))

template<class T>inline T sqr(T x){return x*x;}

template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}

template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

const DB EPS=1e-;

inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}

const DB Pi=acos(-1.0);

inline int gint()

  {

        int res=;bool neg=;char z;

        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

        if(z==EOF)return ;

        if(z=='-'){neg=;z=getchar();}

        for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

        return (neg)?-res:res;

    }

inline LL gll()

  {

      LL res=;bool neg=;char z;

        for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

        if(z==EOF)return ;

        if(z=='-'){neg=;z=getchar();}

        for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

        return (neg)?-res:res;

    }

const int maxN=;

int N,Q;

int val[maxN+];

int now,first[maxN+];

struct Tedge{int v,next;}edge[*maxN+];

inline void addedge(int u,int v){now++;edge[now].v=v;edge[now].next=first[u];first[u]=now;}

int head,tail,que[maxN+];

int fa[maxN+],size[maxN+],heavyson[maxN+],gao[maxN+];

int cnt,idx[maxN+],l[maxN+],r[maxN+];

int vis[maxN+],top,sta[maxN+],last[maxN+];

inline void build()

  {

      int i,j;

      que[head=tail=]=;

      while(head<=tail)

        {

            int u=que[head++],v;

            for(i=first[u],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)if(v!=fa[u])fa[que[++tail]=v]=u;

        }

      red(j,tail,)

        {

            int u=que[j],v;

            size[u]=;

            for(i=first[u],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)if(v!=fa[u])size[u]+=size[v];

        }

      re(j,,tail)

        {

            int u=que[j],v,heavy=-;

            for(i=first[u],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)if(v!=fa[u])

              if(heavy==- || size[heavy]<size[v]) heavy=v;

            heavyson[u]=heavy;

        }

      vis[sta[top=]=]=;

      last[]=first[];

      idx[]=++cnt;

      gao[]=;

      while(top>=)

        {

            int u=sta[top],i=last[u],v;

            if(heavyson[u]!=- && !vis[heavyson[u]])

              {

                  v=heavyson[u];

                      vis[sta[++top]=v]=;

                        last[v]=first[v];

                        idx[v]=++cnt;

                        gao[v]=gao[u];

                    }

                else

                  for(v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)if(v!=fa[u] && !vis[v])

                    {

                        vis[sta[++top]=v]=;

                            last[v]=first[v];

                            idx[v]=++cnt;

                            gao[v]=v;

                            last[u]=edge[i].next;

                            break;

                        }

                if(i==-)top--;

            }

        red(j,tail,)

          {

              int u=que[j],v;

              l[u]=r[u]=idx[u];

              for(i=first[u],v=edge[i].v;i!=-;i=edge[i].next,v=edge[i].v)if(v!=fa[u])upmin(l[u],l[v]),upmax(r[u],r[v]);

          }

    }

struct Ttree{LL v,add;}tr[*maxN+];

inline void down(int rt,int l,int r,int mid)

  {

      if(tr[rt].add==)return;

      LL add=tr[rt].add;

      tr[rt*].add+=add;tr[rt*].v+=add*LL(mid-l+);

      tr[rt*+].add+=add;tr[rt*+].v+=add*LL(r-mid);

      tr[rt].add=;

  }

inline void update(int rt,int l,int r,int x,int y,LL val)

  {

      if(l>r || x>y || y<l || r<x)return;

      if(x<=l && r<=y){tr[rt].add+=val;tr[rt].v+=val*LL(r-l+);return;}

        int mid=(l+r)>>;

      down(rt,l,r,mid);

      update(rt*,l,mid,x,y,val);

      update(rt*+,mid+,r,x,y,val);

      tr[rt].v=tr[rt*].v+tr[rt*+].v;

  }

inline LL ask(int rt,int l,int r,int x,int y)

  {

      if(l>r || x>y || y<l || r<x)return ;

      if(x<=l && r<=y)return tr[rt].v;

      int mid=(l+r)>>;

      down(rt,l,r,mid);

      return ask(rt*,l,mid,x,y)+ask(rt*+,mid+,r,x,y);

  }

inline LL query(int x)

  {

      LL res=;

      while(x)

        {

            res+=ask(,,N,idx[gao[x]],idx[x]);

            x=fa[gao[x]];

        }

      return res;

  }

int main()

  {

      freopen("bzoj4034.in","r",stdin);

      freopen("bzoj4034.out","w",stdout);

      int i;

      N=gint();Q=gint();

      re(i,,N)val[i]=gint();

      now=-;mmst(first,-);

      re(i,,N-){int u=gint(),v=gint();addedge(u,v);addedge(v,u);}

      build();

      re(i,,N)update(,,N,idx[i],idx[i],LL(val[i]));

      while(Q--)

        {

            int type=gint(),x,a;

            switch(type)

              {

                  case :

                      x=gint();a=gint();

                      update(,,N,idx[x],idx[x],LL(a));

                  break;

                  case :

                      x=gint();a=gint();

                      update(,,N,l[x],r[x],LL(a));

                  break;

                  case :

                      x=gint();

                      //PF("%lld\n",query(x));

                      cout<<query(x)<<endl;

                  break;

              }

        }

      return ;

  }