BZOJ 2836: 魔法树

Descrption

一棵树，给一条路径增加权值，询问子树和.\(n\leqslant 10^5\)

Solution

树链剖分.

划水...

Code

/**************************************************************
    Problem: 2836
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:5424 ms
    Memory:19080 kb
****************************************************************/
 
#include 
using namespace std;
 
typedef long long ll;
const int N = 100050;
 
inline int in(int x=0,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x; }
 
int n,q;
 
namespace Seg {
    #define mid ((l+r)>>1)
    #define lc (o<<1)
    #define rc (o<<1|1)
     
    ll d[N<<2],tg[N<<2];
     
    void T(int o,int l,int r,ll v) {
        d[o]+=(r-l+1)*v,tg[o]+=v;
    }
    void Push(int o,int l,int r) {
        if(l!=r) T(lc,l,mid,tg[o]),T(rc,mid+1,r,tg[o]);
        tg[o]=0;return;
    }
    void Update(int o) { d[o]=d[lc]+d[rc]; }
    void Add(int o,int l,int r,int L,int R,ll v) {
        Push(o,l,r);
        if(L<=l && r<=R) { T(o,l,r,v);return; }
        if(L<=mid) Add(lc,l,mid,L,R,v);
        if(R>mid) Add(rc,mid+1,r,L,R,v);
        Update(o);
    }
    ll Query(int o,int l,int r,int L,int R) {
        Push(o,l,r);
        if(L<=l && r<=R) return d[o];
        ll res=0;
        if(L<=mid) res+=Query(lc,l,mid,L,R);
        if(R>mid) res+=Query(rc,mid+1,r,L,R);
        return res;
    }
};
 
namespace Tree {
    vector g[N];
    int cp,sz[N],tp[N],f[N],d[N],sn[N],pp[N],pd[N];
     
    void AddEdge(int u,int v) { g[u].push_back(v),g[v].push_back(u); }
    void DFS1(int u,int fa) {
        f[u]=fa,sz[u]=1,sn[u]=0,d[u]=d[fa]+1;
        for(int i=0,v;i<(int)g[u].size();i++) if((v=g[u][i])!=fa) {
            DFS1(v,u),sz[u]+=sz[v];
            if(!sn[u] || sz[sn[u]]d[v]) swap(u,v);
        Seg::Add(1,1,n,pp[u],pp[v],x);
    }
}
 
int main() {
    n=in();
    for(int i=1,u,v;i