本文主要是介绍HDU 3974 Assign the task 线段树（树映射到区间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意....
题解：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;#define MAXN 100001
#define L(u) (u<<1)
#define R(u) (u<<1|1)struct A_NODE
{A_NODE *sun, *bro;int num;
} anode[MAXN], *aroot;struct R_NODE
{int l, r;
} ran[MAXN];struct NODE
{int l, r, val;
} node[MAXN*3];bool vis[MAXN];
int n, tim, t[MAXN]; //tim从1开始, t[i]记录节点i被访问的次序void add(int u, int v)
{if(anode[u].sun == NULL)anode[u].sun = &anode[v];else{A_NODE *tmp = anode[u].sun;anode[v].bro = tmp->bro;tmp->bro = &anode[v];}
}void A_build()
{int u, v;bool flag[MAXN] = {0};for(int i = 1; i <= n; i++){anode[i].num = i;anode[i].bro = anode[i].sun = NULL;}for(int i = 1; i < n; i++){scanf("%d%d", &v, &u);flag[v] = true;add(u, v);}for(int i = 1; i <= n; i++)if(flag[i] == false) { aroot = &anode[i]; break;}
}void dfs(A_NODE *rt)
{if(rt == NULL) return;int v = rt->num;vis[v] = true;ran[v].l = ++tim;t[v] = tim;A_NODE *p = rt->sun;while(p != NULL){if(!vis[p->num]) dfs(p);p = p->bro;}ran[v].r = tim;
}void build(int u, int l, int r)
{node[u].l = l;node[u].r = r;node[u].val = -1;if(l == r) return;int mid = (l + r) >> 1;build(L(u), l, mid);build(R(u), mid + 1, r);
}void down(int u)
{if(node[u].val != -2){node[L(u)].val = node[R(u)].val = node[u].val;node[u].val = -2;}
}void update(int u, int l, int r, int val)
{if(node[u].l == l && node[u].r == r){node[u].val = val;return;}down(u);int mid = (node[u].l + node[u].r) >> 1;if(r <= mid) update(L(u), l, r, val);else if(l > mid) update(R(u), l, r, val);else {update(L(u), l, mid, val); update(R(u), mid + 1, r, val);}
}int query(int u, int x)
{if(node[u].val != -2)return node[u].val;if(node[u].l == x && node[u].r == x)return node[u].val;int mid = (node[u].l + node[u].r) >> 1;if(x <= mid) return query(L(u), x);else return query(R(u), x);
}int main()
{int T;scanf("%d", &T);for(int cs = 1; cs <= T; cs++){scanf("%d", &n);A_build();tim = 0;memset(vis, 0, sizeof(vis));dfs(aroot);//for(int i = 1; i <= n; i++)//printf("ran[%d]: %d %d\n", i, ran[i].l, ran[i].r);build(1, 1, n);int m, x, y;char oper[3];scanf("%d", &m);printf("Case #%d:\n", cs);while(m--){scanf("%s", oper);if(oper[0] == 'C'){scanf("%d",&x);printf("%d\n", query(1, t[x]));}else{scanf("%d%d",&x,&y);update(1, ran[x].l, ran[x].r, y);}}}return 0;
}
这篇关于HDU 3974 Assign the task 线段树（树映射到区间）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
