[XJOI-NOI2015-13-C]白黑树

题目大意：
　　给你一个$n(n\leq300000)$个结点的以$1$为根的树，结点有黑白两种颜色，每个点初始权值为$0$。进行以下2种共$m(m\leq300000)$次操作：
　　　　1.给定结点$u$，对于所有的黑点$v$，令${\rm LCA}(u,v)$的权值加上$v$；
　　　　2.改变$u$的颜色。

思路：
　　考虑没有操作2的情况，我们可以记录所有结点被询问的次数和所有黑点的编号。最后统计答案时，只需要一个树形DP，求出每个子树内被询问的次数$cnt$和所有黑点的编号之和$sum$即可。$w[x]=\sum cnt[y]\times(sum[x]-sum[y])$。
　　考虑加上操作2，本质上就是多了一个表示时间的维度，考虑使用线段树降维，树形DP时只需要线段树合并更新答案即可。时间复杂度$O(n\log n)$。

 #include<list>

 #include<cstdio>

 #include<cctype>

 typedef long long int64;

 inline int getint() {

     register char ch;

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

     register int x=ch^'';

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

     return x;

 }

 const int N=;

 bool s[N];

 int64 w[N];

 int m,last[N];

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

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

     e[u].push_back(v);

     e[v].push_back(u);

 }

 class SegmentTree {

     private:

         struct Node {

             int cnt;

             int64 sum;

             Node *left,*right;

         };

     public:

         Node *root[N];

         void modify(Node *&p,const int &b,const int &e,const int &l,const int &r,const int &x,const int &y) {

             p=p?:new Node();

             p->cnt+=x;

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

                 p->sum+=y;

                 return;

             }

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

             if(l<=mid) modify(p->left,b,mid,l,std::min(mid,r),x,y);

             if(r>mid) modify(p->right,mid+,e,std::max(mid+,l),r,x,y);

         }

         void merge(Node *&p,Node *const &q,const int &b,const int &e,const int &id) {

             if(!p||!q) {

                 p=p?:q;

                 return;

             }

             w[id]+=p->cnt*q->sum+q->cnt*p->sum;

             p->cnt+=q->cnt;

             p->sum+=q->sum;

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

             merge(p->left,q->left,b,mid,id);

             merge(p->right,q->right,mid+,e,id);

             delete q;

         }

 };

 SegmentTree t;

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

     for(std::list<int>::iterator i=e[x].begin();i!=e[x].end();i++) {

         const int &y=*i;

         if(y==par) continue;

         dfs(y,x);

         t.merge(t.root[x],t.root[y],,m,x);

     }

 }

 int main() {

     const int n=getint();m=getint();

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

         last[i]=s[i]=getint();

     }

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

         add_edge(getint(),getint());

     }

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

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

         if(opt==) {

             t.modify(t.root[u],,m,i,i,,);

             if(s[u]) w[u]+=u;

         }

         if(opt==) {

             if(s[u]^=) {

                 last[u]=i;

             } else {

                 if(i!=) t.modify(t.root[u],,m,last[u],i-,,u);

             }

         }

     }

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

         if(s[i]) t.modify(t.root[i],,m,last[i],m,,i);

     }

     dfs(,);

     for(register int i=;i<=n;i++) printf("%lld\n",w[i]);

     return ;

 }

巴特西

[XJOI-NOI2015-13-C]白黑树

最新文章

热门文章