[LOJ6208]树上询问

题目大意：
　　有一棵n节点的树，根为1号节点。每个节点有两个权值ki,ti，初始值均为0。
　　给出三种操作：
　　　　1.Add(x,d)操作：将x到根的路径上所有点的ki←ki+d
　　　　2.Mul(x,d)操作：将x到根的路径上所有点的ti←ti+d×ki
　　　　3.Query(x)操作：询问点x的权值tx

思路：
　　树链剖分以后用线段树维护。
　　对于每个结点，我们可以维护3个数a,b,c，表示最后的t为a*b+c。
　　对于操作1，需要修改a（修改后的ki）和c（修改的数再乘以b就多了，要从c中减去）。
　　对于操作2，需要修改b。
　　然后操作3就变成了单点查询。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 inline int getint() {

     register char ch;

     register bool neg=false;

     while(!isdigit(ch=getchar())) if(ch=='-') neg=true;

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return neg?-x:x;

 }

 const int N=;

 std::vector<int> e[N];

 inline void add_edge(const int &u,const int &v) {

     e[u].push_back(v);

     e[v].push_back(u);

 }

 int n,par[N],son[N],size[N],dep[N],top[N],id[N];

 void dfs1(const int &x,const int &par) {

     size[x]=;

     ::par[x]=par;

     dep[x]=dep[par]+;

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         dfs1(y,x);

         size[x]+=size[y];

         if(size[y]>size[son[x]]) {

             son[x]=y;

         }

     }

 }

 void dfs2(const int &x) {

     id[x]=++id[];

     if(x==son[par[x]]) {

         top[x]=top[par[x]];

     } else {

         top[x]=x;

     }

     if(son[x]) dfs2(son[x]);

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par[x]||y==son[x]) continue;

         dfs2(y);

     }

 }

 struct Tag {

     int a,b,c;

     void operator += (const Tag &another) {

         c+=another.c-another.a*b;

         a+=another.a;

         b+=another.b;

     }

     int calc() const {

         return a*b+c;

     }

 };

 class SegmentTree {

     #define _left <<1

     #define _right <<1|1

     private:

         Tag val[N<<];

         void push_down(const int &p) {

             val[p _left]+=val[p];

             val[p _right]+=val[p];

             val[p]=(Tag){,,};

         }

     public:

         void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const Tag &t) {

             if(b==l&&e==r) {

                 val[p]+=t;

                 return;

             }

             push_down(p);

             const int mid=(b+e)>>;

             if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),t);

             if(r>mid) modify(p _right,mid+,e,std::max(mid+,l),r,t);

         }

         int query(const int &p,const int &b,const int &e,const int &x) {

             if(b==e) {

                 return val[p].calc();

             }

             push_down(p);

             const int mid=(b+e)>>;

             return x<=mid?query(p _left,b,mid,x):query(p _right,mid+,e,x);

         }

     #undef _left

     #undef _right

 };

 SegmentTree t;

 inline void modify(int x,const Tag &tag) {

     for(;top[x];x=par[top[x]]) {

         t.modify(,,n,id[top[x]],id[x],tag);

     }

 }

 inline int query(const int &x) {

     return t.query(,,n,id[x]);

 }

 int main() {

     n=getint();

     for(register int i=;i<n;i++) {

         add_edge(getint(),getint());

     }

     dfs1(,);

     dfs2();

     for(register int m=getint();m;m--) {

         const int opt=getint(),x=getint();

         if(opt==) modify(x,(Tag){getint(),,});

         if(opt==) modify(x,(Tag){,getint(),});

         if(opt==) printf("%d\n",query(x));

     }

     return ;

 }

巴特西

[LOJ6208]树上询问

最新文章

热门文章