数树数
题目描述
给定一棵N个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作：
1. C i x(0<=x<2^31) 表示将i点权值变为x
2. Q i j x(0<=x<2^31) 表示询问i到j的路径上有多少个值为x的节点
输入
对于每个测试点，第一行有两个整数N,Q，分别表示树上节点个数询问个数。下面一行N个整数，表示初始时每个点的权值。接下来N-1行，每行两个整数x,y，表示x与y之间有边。接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。
对于30%的数据，N,Q<=1000；
对于100%的数据，N<=100000,Q<=200000。
输出
对于每个Q输出一行所求的答案。
样例输入
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
样例输出
0
1
1
0考虑对每个权值开线段树，下标为点的编号
维护点的数目和
修改就把相应的两种权值的树拉出来
查询就树剖+区间查询
树不能开满，那就动态开
似乎很像旅行
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 100005
using namespace std;
int n,T,Q,head[maxn],s[maxn],lsh[maxn*3],dy[maxn*3],t1,t2,tot,fs,total;
int size[maxn],son[maxn],fa[maxn],top[maxn],deep[maxn],sc,dfsn[maxn],fsy,li,ri,root[maxn*3];
map<int,int>l;
char ch;
struct node{
int v,nex;
}e[maxn*2];
struct no{
int id,a,b,c;
}q[maxn*2];
struct ff{
int x,ls,rs,l,r;
}tree[maxn*3*21];
void lj(int t1,int t2){
total++;e[total].v=t2;e[total].nex=head[t1];head[t1]=total;
}
void Lsh(){
sort(lsh+1,lsh+tot+1);
lsh[0]=-1;
for(int i=1;i<=tot;i++){
if(lsh[i]!=lsh[i-1])l[lsh[i]]=++fs,dy[fs]=lsh[i];
}
}
void dfs1(int k,int fath){
fa[k]=fath;deep[k]=deep[fath]+1;
int sz=0,gp=-1;
for(int i=head[k];i;i=e[i].nex){
if(e[i].v!=fath){
dfs1(e[i].v,k);
sz+=size[e[i].v];
if(gp==-1)gp=e[i].v;
if(size[e[i].v]>size[gp])gp=e[i].v;
}
}
size[k]=sz+1;son[k]=gp;
}
void dfs2(int k){
dfsn[k]=++sc;
if(son[k]!=-1){
top[son[k]]=top[k];
dfs2(son[k]);
}
for(int i=head[k];i;i=e[i].nex){
if(e[i].v!=fa[k]&&e[i].v!=son[k]){
top[e[i].v]=e[i].v;
dfs2(e[i].v);
}
}
}
void wh(int k){
tree[k].x=tree[tree[k].ls].x+tree[tree[k].rs].x;
}
void lian(int &k,int l,int r,int pl,int v){
if(!k)k=++fsy;
tree[k].l=l;tree[k].r=r;
if(l==r){
tree[k].x+=v;return;
}
int mid=l+r>>1;
if(pl<=mid)lian(tree[k].ls,l,mid,pl,v);
else lian(tree[k].rs,mid+1,r,pl,v);
wh(k);
}
int ask(int k){
if(!k)return 0;
if(tree[k].l>=li&&tree[k].r<=ri){
return tree[k].x;
}
int mid=tree[k].l+tree[k].r>>1;
int co=0;
if(li<=mid)co+=ask(tree[k].ls);
if(ri>mid)co+=ask(tree[k].rs);
return co;
}
int main(){
cin>>n>>Q;
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
lsh[++tot]=s[i];
}
for(int i=1;i<n;i++){
scanf("%d%d",&t1,&t2);
lj(t1,t2);lj(t2,t1);
}
for(int i=1;i<=Q;i++){
scanf(" %c",&ch);
if(ch=='C'){
q[i].id=1;
scanf("%d%d",&q[i].a,&q[i].b);
lsh[++tot]=q[i].b;
}
else {
scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
lsh[++tot]=q[i].c;
}
}
Lsh();
dfs1(1,0);top[1]=1;dfs2(1);
for(int i=1;i<=n;i++){
int tmp=l[s[i]];
lian(root[tmp],1,n,dfsn[i],1);
}
for(int i=1;i<=Q;i++){
if(q[i].id==1){
int tmp=l[s[q[i].a]];
lian(root[tmp],1,n,dfsn[q[i].a],-1);
s[q[i].a]=q[i].b;
tmp=l[s[q[i].a]];
lian(root[tmp],1,n,dfsn[q[i].a],1);
}
else {
int sum=0,x,y,tmp;
x=q[i].a,y=q[i].b;tmp=l[q[i].c];
t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2])swap(x,y),swap(t1,t2);
li=dfsn[t1];ri=dfsn[x];
sum+=ask(root[tmp]);
x=fa[t1];t1=top[x];
}
if(deep[x]<deep[y])swap(x,y);
li=dfsn[y],ri=dfsn[x];
sum+=ask(root[tmp]);
printf("%d
",sum);
}
}
return 0;
}