DFS序: 先序周遊保留進入和離開某個節點的時間(in和out) out-in+1就是以目前結點為根的樹上的節點個數,out-in就是非根節點的個數,這樣就将關系樹轉化成了線性。
(紅色代表進入時間,綠色代表out的時間)
這樣就得到了每個節點管轄的區間,将标号轉化一下,就可以線段樹了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int T;
int n;
const int maxn = 50000+10;
vector<int>g[maxn];
int cnt;
int in[maxn],out[maxn];
int indegree[maxn];
void DFS(int x)
{
cnt++;
in[x] = cnt;
for(int i = 0 ; i < g[x].size() ; i++)
{
DFS(g[x][i]);
}
out[x] = cnt;
}
void Init()
{
memset(indegree,0,sizeof(indegree));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
cnt = 0;
for(int i = 0 ; i < n ; i++)
{
g[i].clear();
}
}
struct SegTree
{
int l,r;
int job=-1;
int lazy;
} s[maxn<<2];
void pushdown(int i)
{
if(s[i].lazy != -1)
{
s[i<<1].lazy = s[i<<1|1].lazy = s[i].lazy;
s[i<<1].job = s[i].job;
s[i<<1|1].job = s[i].job;
s[i].lazy = -1;
}
}
void build(int l, int r, int i)
{
s[i].l = l;
s[i].r = r;
s[i].lazy = -1;
s[i].job = -1;
if(l == r) return;
int mid = (l+r) >> 1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
}
void update(int l,int r,int i,int x)
{
pushdown(i);
if(l==s[i].l && s[i].r == r)
{
s[i].lazy = 1;
s[i].job = x;
return;
}
int mid = (s[i].l + s[i].r) >> 1;
if(r<=mid)
{
update(l,r,i<<1,x);
}
else if(l>mid)
{
update(l,r,i<<1|1,x);
}
else
{
update(l,mid,i<<1,x);
update(mid+1,r,i<<1|1,x);
}
}
int q;
void query(int pos, int i)
{
pushdown(i);
if(s[i].l == s[i].r)
{
q = s[i].job;
return;
}
int mid = (s[i].l + s[i].r) >> 1;
if(pos <= mid) query(pos,i<<1);
if(pos > mid) query(pos,i<<1|1);
}
int main()
{
cin >> T;
int kase = 1 ;
while(T--)
{
Init();
cin >> n;
int father,son;
for(int i = 0 ; i < n-1 ; i++)
{
cin >> son >> father;
g[father].push_back(son);
indegree[son]++;
}
for(int i = 1 ; i <= n ; i++)
{
if(indegree[i] == 0)
{
DFS(i);
break;
}
}
build(1,cnt,1);
printf("Case #%d:\n",kase++);
int m;
char ch;
cin >> m;
for(int i = 0 ; i < m ; i++)
{
cin >> ch;
if(ch == 'C')
{
int x;
cin >> x;
q = -1;
query(in[x],1);
cout << q << endl;
}
else
{
int pos,to;
cin >> pos >> to;
update(in[pos],out[pos],1,to);
}
}
}
return 0;
}