首页 > 代码库 > BZOJ 2836: 魔法树

BZOJ 2836: 魔法树

Descrption

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

Solution

树链剖分.

划水...

Code

/**************************************************************    Problem: 2836    User: BeiYu    Language: C++    Result: Accepted    Time:5424 ms    Memory:19080 kb****************************************************************/ #include <bits/stdc++.h>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<int> 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]]<sz[v]) sn[u]=v;        }    }    void DFS2(int u,int ttp) {        pp[u]=++cp,tp[u]=ttp;        if(sn[u]) DFS2(sn[u],ttp);        for(int i=0,v;i<(int)g[u].size();i++)            if((v=g[u][i])!=f[u] && v!=sn[u]) DFS2(v,v);        pd[u]=cp;    }    ll Query(int x) { return Seg::Query(1,1,n,pp[x],pd[x]); }    void Add(int u,int v,ll x) {        for(int f1=tp[u],f2=tp[v];f1^f2;) {            if(d[f1]<d[f2]) swap(f1,f2),swap(u,v);            Seg::Add(1,1,n,pp[f1],pp[u],x);            u=f[f1],f1=tp[u];        }        if(d[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<n;i++) u=in(),v=in(),Tree::AddEdge(u,v);    Tree::DFS1(0,0),Tree::DFS2(0,0);    for(q=in();q--;) {        char opt[10];        int u,v,d;        scanf("%s",opt);        if(opt[0]==‘A‘) u=in(),v=in(),d=in(),Tree::Add(u,v,d);        else d=in(),printf("%lld\n",Tree::Query(d));    }    return 0;}

  

BZOJ 2836: 魔法树