性质:dfs序可以把一棵树区间化,即可以求出每个节点的管辖区间。
根据dfs序,记录点的进出栈的时间,把树上问题 转化为区间, 那么就可以套用线段树和树状数组了。
点A所在区间[in[A], out[A]] 那么以A为根的子树区间为[in[A], out[A]]
除此之外给某个节点赋值时,可以直接记录左端点 对应 的顶点
void dfs(int sta, int fa)
{
in[sta] = ++ tim; //相应的dfs序列
id[tim] = sta; // 》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
for(int i = h[sta] ; i != -1 ; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, sta);
}
out[sta] = tim;
}
void build(int rt, int l, int r)
{
tre[rt] = {l, r}; //到了树的底部
if(tre[rt].l == tre[rt].r)
{
tre[rt].sum = val[id[l]];
return ;
}
int mid = tre[rt].mid();
build(rt * 2, l, mid), build(rt * 2 + 1, mid + 1, r);
pushup(rt);
}
Assign the task
树上问题, 区间修改 单点查询
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
int h[maxn], ne[maxn], e[maxn], d[maxn], idx, tim;
int in[maxn], out[maxn];
struct note{
int l;
int r;
int val; //当前的任务
int lazy;
int mid()
{
return (l + r) >> 1;
}
}tre[maxn << 2];
void add(int u, int v)
{
e[idx] = v;
ne[idx] = h[u];
h[u] = idx ++;
}
void dfs(int sta)
{
in[sta] = ++ tim; //相应的dfs序列
for(int i = h[sta] ; i != -1 ; i = ne[i])
{
int j = e[i];
// if(j == fa) continue;
dfs(j);
}
out[sta] = tim;
}
void build(int rt , int l ,int r)
{
tre[rt] = {l, r, 0, 0};
if(tre[rt].l == tre[rt].r)
return ;
int mid = tre[rt].mid();
build(rt * 2, l, mid), build(rt * 2 + 1, mid + 1, r); //根本不需要pushup
}
void pushdown(int rt)
{
if(tre[rt].lazy != 0)
{
tre[rt * 2].val = tre[rt].lazy; //
tre[rt * 2 + 1].val = tre[rt].lazy;
tre[rt * 2].lazy = tre[rt].lazy;
tre[rt * 2 + 1].lazy = tre[rt].lazy;
tre[rt].lazy = 0;
}
}
void modify(int rt , int l, int r, int w)
{
if(tre[rt].l == l && tre[rt].r == r) //当前找到了
{
tre[rt].val = w; //区间修改
tre[rt].lazy = w;
return ;
}
pushdown(rt); //
int mid = tre[rt].mid();
if(r <= mid) //左子树
modify(rt * 2, l, r, w);
else if(l > mid)
modify(rt * 2 + 1, l , r, w);
else
modify(rt * 2, l, mid, w), modify(rt * 2 + 1, mid + 1, r, w);
}
int query(int rt, int l) //单点查询
{
if(tre[rt].l == tre[rt].r)
return tre[rt].val;
pushdown(rt);
int mid = tre[rt].mid();
if(l <= mid)
return query(rt * 2, l);
else
return query(rt * 2 + 1, l);
}
int main()
{
int T;
scanf("%d", &T);//区间修改 单点查询
int cnt = 1;
while(T --)
{
int N;
scanf("%d", &N);
idx = 0, tim = 0;
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
for(int i = 1 ; i < N ; i ++)
{
int u, v;
scanf("%d %d", &u, &v);
add(v, u); d[u] ++;
}
for(int i = 1 ; i <= N; i ++)
{
if(!d[i]) //入度为0 根
{
dfs(i);
}
}
// for(int i = 1 ; i <= N ; i ++)
// printf("%d %d\n", in[i], out[i]);
// printf("\n");
build(1, 1, N);
int M;
scanf("%d", &M);
printf("Case #%d:\n",cnt ++);
for(int i = 1 ; i <= M ; i ++)
{
char op[2];
scanf("%s", op);
int x;
scanf("%d", &x);
if(*op == 'C') //询问当前任务
{
int temp = query(1, in[x]);
printf("%d\n", (temp == 0) ? -1 : temp);
}
else //
{
int y;
scanf("%d", &y); //区间修改为y
modify(1, in[x], out[x], y);
}
}
}
return 0;
}