题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3974
题目大意:给出n个人,m个关系,组成一棵树,一个人得到了任务后,他的所有下属都会做这份工作,问每个区间都有多少个不同的工作
思路:因为一个节点和他所有的子节点共享一个val。很容易想到DFS序,然后建个线段树就好了,区间更新单点查询。
ACCode:
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pii pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=5e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
struct SegTree{
struct Node{
int l,r;
int val;
int lazy;
};
Node Tree[MAXN<<2];
void PushDown(int rt){
if(Tree[rt].lazy!=-1){
Tree[rt<<1].lazy=Tree[rt<<1|1].lazy=Tree[rt].lazy;
Tree[rt<<1].val=Tree[rt<<1|1].val=Tree[rt].lazy;
Tree[rt].lazy=-1;
}
}
void Build(int l,int r,int rt){
Tree[rt].l=l;Tree[rt].r=r;Tree[rt].val=Tree[rt].lazy=-1;
if(l==r) return ;
int mid=(l+r)>>1;
Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);
}
void Update(int ql,int qr,int val,int rt){
if(ql<=Tree[rt].l&&Tree[rt].r<=qr){
Tree[rt].val=Tree[rt].lazy=val;
return ;
}PushDown(rt);
if(qr<=Tree[rt<<1].r) Update(ql,qr,val,rt<<1);
else if(ql>=Tree[rt<<1|1].l) Update(ql,qr,val,rt<<1|1);
else{
Update(ql,qr,val,rt<<1);
Update(ql,qr,val,rt<<1|1);
}
}
int Query(int Pos,int rt){
if(Tree[rt].l==Tree[rt].r) return Tree[rt].val;
PushDown(rt);
if(Pos<=Tree[rt<<1].r) return Query(Pos,rt<<1);
if(Pos>=Tree[rt<<1|1].l) return Query(Pos,rt<<1|1);
}
void Show(int rt){
printf("l=%d r=%d val=%d lazy=%d\n",Tree[rt].l,Tree[rt].r,Tree[rt].val,Tree[rt].lazy);
if(Tree[rt].l==Tree[rt].r) return ;
Show(rt<<1);Show(rt<<1|1);
}
};
struct Node{
int v,nxt;
Node(int _v=0,int _nxt=0){
v=_v;nxt=_nxt;
}
};
SegTree Seg;
Node Edge[MAXN<<4];
int Head[MAXN],Ecnt;
int InDeg[MAXN];
int L[MAXN],Dep[MAXN],R[MAXN],tot;
int n,m;
void Intt(){
clean(Head,-1);Ecnt=0;
clean(InDeg,0);
tot=0;
}
void AddEdge(int u,int v){
Edge[Ecnt]=Node(v,Head[u]);
Head[u]=Ecnt++;
}
void DFS(int u,int fa,int dep){
L[u]=++tot;Dep[u]=dep;
for(int i=Head[u];i+1;i=Edge[i].nxt){
int v=Edge[i].v;
if(v==fa) continue;
DFS(v,u,dep+1);
}R[u]=tot;
}
int main(){
int T,Case=1;scanf("%d",&T);
while(T--){
Intt();printf("Case #%d:\n",Case++);
scanf("%d",&n);
for(int i=2;i<=n;++i){
int a,b;scanf("%d%d",&a,&b);
AddEdge(a,b);AddEdge(b,a);
InDeg[a]++;
}
int rt;
for(int i=1;i<=n;++i){
if(InDeg[i]==0){
rt=i;break;
}
}DFS(rt,-1,0);
Seg.Build(1,n,1);//Seg.Show(1);
scanf("%d",&m);
while(m--){
char opt[5];scanf("%s",&opt);
if(opt[0]=='C'){
int Pos;scanf("%d",&Pos);
printf("%d\n",Seg.Query(L[Pos],1));
}
else{
int Pos,val;scanf("%d%d",&Pos,&val);
Seg.Update(L[Pos],R[Pos],val,1);
}//Seg.Show(1);
}
}
}