[CF607D]Power Tree

题目大意：
　　一棵树初始只有一个编号为$1$的权值为$w_1$的根。$q(q\le2\times10^5)$次操作，每次可以给出$v,w(w<10^9)$，新建一个结点作为$v$的子结点，权值为$w$；或者给出$u$，求出$f(u)$。定义$f(u)=|S|\cdot\sum_{d\in S}d$，其中$S$为$w_u$与其所有子结点$v$的$f(v)$构成的可重集合。

思路：
　　首先将树全部建好，用线段树维护DFS序。每次新加结点相当于将这一结点的权值由$0$变为$w$，用线段树计算加上这个点以后的贡献。题目就变成了线段树上单点加、区间乘、区间求和问题。时间复杂度$O(q(\log n+\log w))$，其中$O(\log w)$是求逆元的复杂度。

 #include<cstdio>

 #include<cctype>

 #include<forward_list>

 using int64=long long;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

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

     return x;

 }

 constexpr int N=2e5+,Q=2e5,mod=1e9+;

 int w[N],n,dfn[N],par[N],size[N],s[N];

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

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

     e[u].push_front(v);

 }

 struct Operation {

     int type,v,u;

 };

 Operation o[N];

 void exgcd(const int &a,const int &b,int &x,int &y) {

     if(!b) {

         x=,y=;

         return;

     }

     exgcd(b,a%b,y,x);

     y-=a/b*x;

 }

 int inv(const int &x) {

     int ret,tmp;

     exgcd(x,mod,ret,tmp);

     return (ret%mod+mod)%mod;

 }

 void dfs(const int &x) {

     size[x]=;

     dfn[x]=++dfn[];

     for(auto &y:e[x]) {

         dfs(y);

         size[x]+=size[y];

     }

 }

 class SegmentTree {

     #define _left <<1

     #define _right <<1|1

     private:

         int val[N<<],tag[N<<];

         void push_up(const int &p) {

             val[p]=(val[p _left]+val[p _right])%mod;

         }

         void push_down(const int &p) {

             if(tag[p]==) return;

             tag[p _left]=(int64)tag[p _left]*tag[p]%mod;

             tag[p _right]=(int64)tag[p _right]*tag[p]%mod;

             val[p _left]=(int64)val[p _left]*tag[p]%mod;

             val[p _right]=(int64)val[p _right]*tag[p]%mod;

             tag[p]=;

         }

     public:

         void build(const int &p,const int &b,const int &e) {

             tag[p]=;

             if(b==e) return;

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

             build(p _left,b,mid);

             build(p _right,mid+,e);

         }

         void add(const int &p,const int &b,const int &e,const int &x,const int &v) {

             (val[p]+=v)%=mod;

             if(b==e) return;

             push_down(p);

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

             if(x<=mid) add(p _left,b,mid,x,v);

             if(x>mid) add(p _right,mid+,e,x,v);

         }

         void mul(const int &p,const int &b,const int &e,const int &l,const int &r,const int &v) {

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

                 val[p]=(int64)val[p]*v%mod;

                 tag[p]=(int64)tag[p]*v%mod;

                 return;

             }

             push_down(p);

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

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

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

             push_up(p);

         }

         int query(const int &p,const int &b,const int &e,const int &l,const int &r) {

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

                 return val[p];

             }

             push_down(p);

             int ret=;

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

             if(l<=mid) (ret+=query(p _left,b,mid,l,std::min(mid,r)))%=mod;

             if(r>mid) (ret+=query(p _right,mid+,e,std::max(mid+,l),r))%=mod;

             return ret;

         }

     #undef _left

     #undef _right

 };

 SegmentTree t;

 int main() {

     w[n=]=getint();

     const int q=getint();

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

         o[i].type=getint();

         if(o[i].type==) {

             o[i].v=par[++n]=getint();

             add_edge(par[n],n);

             w[o[i].u=n]=getint();

         }

         if(o[i].type==) {

             o[i].v=getint();

         }

     }

     dfs();

     s[]=;

     t.build(,,n);

     t.add(,,n,,w[]);

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

         const int &y=o[i].u,&x=o[i].v;

         if(o[i].type==) {

             t.add(,,n,dfn[y],(int64)t.query(,,n,dfn[x],dfn[x])*inv(w[x])%mod*w[y]%mod);

             t.mul(,,n,dfn[x],dfn[x]+size[x]-,(int64)inv(s[x])*(s[x]+)%mod);

             s[x]+=s[y]=;

         }

         if(o[i].type==) {

             const int ans=t.query(,,n,dfn[x],dfn[x]+size[x]-);

             if(x==) {

                 printf("%d\n",ans);

                 continue;

             }

             printf("%d\n",int((int64)ans*w[par[x]]%mod*inv(t.query(,,n,dfn[par[x]],dfn[par[x]]))%mod));

         }

     }

     return ;

 }

巴特西

[CF607D]Power Tree

最新文章

热门文章