题解loj146，dfs序3

  1 #include<cstdio>
  2 #define it register int
  3 #define il inline
  4 const int N=8000005;
  5 typedef long long ll;
  6 int h[N],nxt[N],adj[N],opt,l[N],r[N],s[N],id[N],root,u,v,k,d[N],n,m,fa[N],top[N],w[N],son[N],t,cnt,lc;
  7 ll ans,ww[N],c1[N],c2[N];
  8 namespace io {
  9     const int SIZE = (1 << 21) + 1;
 10     char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
 11     int f, qr;
 12 #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
 13     inline void flush () {
 14         fwrite (obuf, 1, oS - obuf, stdout);
 15         oS = obuf;
 16     }
 17     inline void putc (char x) {
 18         *oS ++ = x;
 19         if (oS == oT) flush ();
 20     }
 21     template<class T>
 22     inline void getc(T &x)
 23     {
 24         for(c=gc();!((c>='a'&&c<='z')||(c>='A'&&c<='Z'));c=gc());
 25         x=c;
 26     }
 27     template <class I>
 28     inline void fr (I &x) {
 29         for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
 30         for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
 31         x *= f;
 32     }
 33     template <class I>
 34     inline void print (I x) {
 35         if (!x) putc ('0');
 36         if (x < 0) putc ('-'), x = -x;
 37         while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
 38         while (qr) putc (qu[qr --]);
 39     }
 40     struct Flusher_ {
 41         ~Flusher_() {
 42             flush();
 43         }
 44     } io_flusher_;
 45 }
 46 using io :: fr;
 47 using io :: putc;
 48 using io :: print;
 49 using io :: getc;
 50 il void Add(){
 51     nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u;
 52 }
 53 il void DFS(it x){
 54     s[x]=1,d[x]=d[fa[x]]+1,l[x]=++cnt,ww[x]=w[x];
 55     for(it i=h[x];i;i=nxt[i])
 56         if(adj[i]!=fa[x]){
 57             fa[adj[i]]=x,DFS(adj[i]),s[x]+=s[adj[i]],ww[x]+=ww[adj[i]];
 58             if(s[adj[i]]>s[son[x]])
 59                 son[x]=adj[i];
 60         }
 61     r[x]=cnt;
 62 }
 63 il void dfs(it x){ 
 64     if(!top[x]) top[x]=x;
 65     if(!son[x]) return;
 66     top[son[x]]=top[x],dfs(son[x]);
 67     for(it i=h[x];i;i=nxt[i])
 68         if(adj[i]!=fa[x]&&adj[i]!=son[x]) dfs(adj[i]);
 69 }
 70 il void sp(int &p,int &q){
 71     p+=q,q=p-q,p-=q;
 72 }
 73 il void lca(){
 74     it p=u,q=v;
 75     while(top[p]!=top[q]){
 76         if(d[top[p]]<d[top[q]]) sp(p,q);
 77         p=fa[top[p]];
 78     }
 79     lc=d[p]<d[q]?p:q;
 80 }
 81 il ll cal(ll *t,it x){
 82     ll now=0;
 83     while(x) now+=t[x],x-=(x&-x);
 84     return now;
 85 }
 86 il void add(ll *t,it x,ll num){
 87     while(x<=n) t[x]+=num,x+=(x&-x);
 88 }
 89 il ll q(ll *t,it l,it r){
 90     return cal(t,r)-cal(t,l-1);
 91 }
 92 il void ins(it x){
 93     add(c1,l[x],k),add(c2,l[x],1ll*k*d[x]);
 94 }
 95 il void del(it x){
 96     add(c1,l[x],-k),add(c2,l[x],-1ll*k*d[x]);
 97 }
 98 int main(){ 
 99     fr(n),fr(m),fr(root);
100     for(it i=1;i<=n;++i) fr(w[i]);
101     for(it i=1;i<n;++i) fr(u),fr(v),Add();
102     DFS(root),dfs(root);
103     while(m--){
104         fr(opt),fr(u); 
105         if(opt==1){
106             fr(v),fr(k),lca();
107             ins(u),ins(v),del(lc);
108             if(fa[lc]) del(fa[lc]);
109         }
110         if(opt==2) printf("%lld
",q(c1,l[u],r[u])+w[u]);
111         if(opt==3) printf("%lld
",q(c2,l[u],r[u])+1ll*q(c1,l[u],r[u])*(1-d[u])+ww[u]);
112     }
113     return 0;
114 }
View Code
完美的树状数组+树上差分+树链剖分。。