BZOJ 4999 This Problem Is Too Simple！-白红宇

BZOJ 4999 This Problem Is Too Simple！

阅读量：6839 次

发布时间：2019-06-26

本文共 2201 字，大约阅读时间需要 7 分钟。

Description

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

现在支持以下两种操作：

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

Sample Output

题解：

　　这个题目，树链剖分是十分显然的，但怎么查询权值为x的节点个数呢？

　　可以为每个权值都开一棵线段树，当然要动态开点，因为开不下，所以离散化一下就可以了。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #define MAXN 100010using namespace std;struct edge{ int first; int next; int to;}a[MAXN*2];struct tree{ int ls,rs,sum;}tr[5000010];int dep[MAXN],son[MAXN],size[MAXN],fa[MAXN],top[MAXN],dfn[MAXN],w[MAXN];int numed=0,numtr=0,numcl=0,numdfn=0,n,q;int roof[MAXN*3],color[MAXN];map
            
              mp;char s[3];void addedge(int from,int to){ a[++numed].to=to; a[numed].next=a[from].first; a[from].first=numed;}void dfs1(int now,int f){ fa[now]=f,dep[now]=dep[f]+1,size[now]=1; for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==f) continue; dfs1(to,now); if(size[to]>size[son[now]]) son[now]=to; size[now]+=size[to]; }}void dfs2(int now,int tp){ top[now]=tp;dfn[now]=++numdfn; if(son[now]) dfs2(son[now],tp); for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==fa[now]||to==son[now]) continue; dfs2(to,to); }}void change(int &x,int l,int r,int pos,int zhi){ if(!x) x=++numtr; if(l==r&&l==pos){ tr[x].sum+=zhi; return; } int mid=(l+r)/2; if(pos<=mid) change(tr[x].ls,l,mid,pos,zhi); else change(tr[x].rs,mid+1,r,pos,zhi); tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;}int query(int x,int L,int R,int l,int r){ if(!x) return 0; if(L==l&&R==r){ return tr[x].sum; } int mid=(L+R)/2; if(r<=mid) return query(tr[x].ls,L,mid,l,r); else if(l>mid) return query(tr[x].rs,mid+1,R,l,r); else return query(tr[x].ls,L,mid,l,mid)+query(tr[x].rs,mid+1,R,mid+1,r);}int work(int x,int y,int rf){ int topx=top[x],topy=top[y],ans=0; while(topx!=topy){ if(dep[topx]