[BZOJ 4999]This Problem Is Too Simple!

题目

给您一颗树，每个节点有个初始值。

现在支持以下两种操作：

1. C i x(0<=x<2^31) 表示将i节点的值改为x。

2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点。

INPUT

第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数。

下面一行N个整数，表示初始时每个节点的初始值。

接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）。

接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。

OUTPUT

对于每个Q输出单独一行表示所求的答案。

SAMPLE

INPUT

5 6
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 3 40
C 1 40
Q 2 3 40
Q 4 5 30
C 3 10
Q 4 5 30

OUTPUT

0

1

1

0

解题报告

树剖+权值线段树动态开点+离散

随便搞搞就行了

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 using namespace std;

 inline int read(){

     int sum();

     char ch(getchar());

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 struct edge{

     int e;

     edge *n;

 }ed[],*pre[];

 int tot;

 inline void insert(int s,int e){

     ed[++tot].e=e;

     ed[tot].n=pre[s];

     pre[s]=&ed[tot];

 }

 map<int,int>ma;

 int num;

 int n,q;

 int a[];

 int dep[],size[],fa[],son[];

 inline void dfs1(int u){

     size[u]=;

     son[u]=;

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(e!=fa[u]){

             fa[e]=u;

             dep[e]=dep[u]+;

             dfs1(e);

             size[u]+=size[e];

             if(size[e]>size[son[u]])

                 son[u]=e;

         }

     }

 }

 int timee;

 int id[],pos[],top[];

 inline void dfs2(int u,int rt){

     top[u]=rt;

     id[u]=++timee;

     pos[timee]=u;

     if(son[u])

         dfs2(son[u],rt);

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(e!=fa[u]&&e!=son[u])

             dfs2(e,e);

     }

 }

 int cnt;

 int rt[],lch[],rch[],sum[];

 inline void update(int &x,int pos,int w,int l,int r){

     if(!x)

         x=++cnt;

     sum[x]+=w;

     if(l==r)

         return;

     int mid((l+r)>>);

     if(pos<=mid)

         update(lch[x],pos,w,l,mid);

     else

         update(rch[x],pos,w,mid+,r);

 }

 inline int query(int x,int ll,int rr,int l,int r){

     if(!x)

         return ;

     if(ll<=l&&r<=rr)

         return sum[x];

     int mid((l+r)>>),ret();

     if(ll<=mid)

         ret+=query(lch[x],ll,rr,l,mid);

     if(mid<rr)

         ret+=query(rch[x],ll,rr,mid+,r);

     return ret;

 }

 inline int ask(int x,int y,int z){

     int ret(),tmp(ma[z]);

     while(top[x]^top[y]){

         if(dep[top[x]]<dep[top[y]])

             swap(x,y);

         ret+=query(rt[tmp],id[top[x]],id[x],,n);

         x=fa[top[x]];

     }

     if(dep[x]>dep[y])

         swap(x,y);

     ret+=query(rt[tmp],id[x],id[y],,n);

     return ret;

 }

 char op[];

 int main(){

     memset(pre,NULL,sizeof(pre));

     n=read(),q=read();

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

         a[i]=read();

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

         int x(read()),y(read());

         insert(x,y),insert(y,x);

     }

     dfs1();

     dfs2(,);

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

         if(!ma[a[i]])

             ma[a[i]]=++num;

         update(rt[ma[a[i]]],id[i],,,n);

     }

     while(q--){

         scanf("%s",op);

         if(op[]=='C'){

             int x(read()),y(read());

             update(rt[ma[a[x]]],id[x],-,,n);

             if(!ma[y])

                 ma[y]=++num;

             a[x]=y;

             update(rt[ma[y]],id[x],,,n);

         }

         else{

             int x(read()),y(read()),z(read());

             if(!ma[z])

                 puts("");

             else

                 printf("%d\n",ask(x,y,z));

         }

     }

 }

巴特西

[BZOJ 4999]This Problem Is Too Simple!

[BZOJ 4999]This Problem Is Too Simple!

题目

INPUT

OUTPUT

SAMPLE

INPUT

OUTPUT

解题报告

最新文章

热门文章