kuangbin专题七 HDU3974 Assign the task (dfs时间戳建树)
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
InputThe first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
"C x" which means an inquiry for the current task of employee x
or
"T x y"which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)OutputFor each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.Sample Input
1
5
4 3
3 2
1 3
5 2
5
C 3
T 2 1
C 3
T 3 2
C 3
Sample Output
Case #1:
-1
1
2 读题之后发现建树是个问题,然后就学习了dfs建树。有一个结论,如果v是u的祖先,那么dfs序st[v]<st[u]&&ed[v]>ed[u] 于是就可以建树了。然后就是打标记查标记
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
using namespace std;
#define FO freopen("in.txt","r",stdin);
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define debug(x) cout << "&&" << x << "&&" << endl;
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a, b, sizeof(a));
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=;
const int inf = 0x3f3f3f3f;
ll powmod(ll a,ll b) {ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//head const int maxn=;
int _,lazy[maxn<<],st[maxn],ed[maxn],cur,m,vis[maxn],n;
vector<int> boss[maxn]; void dfs(int rt) {//建树
st[rt]=++cur;
for(int i=;i<boss[rt].size();i++) {
dfs(boss[rt][i]);
}
ed[rt]=cur;
} void pushdown(int rt) {
if(lazy[rt]!=-) {
lazy[rt<<]=lazy[rt];
lazy[rt<<|]=lazy[rt];
lazy[rt]=-;
}
} void build(int rt,int L,int R) {
lazy[rt]=-;
if(L==R) return;
int mid=(L+R)>>;
build(rt<<,L,mid);
build(rt<<|,mid+,R);
} void updata(int rt,int L,int R,int l,int r,int zhi) {
if(L>=l&&R<=r) {
lazy[rt]=zhi;
return;
}
pushdown(rt);
int mid=(L+R)>>;
if(l<=mid) updata(rt<<,L,mid,l,r,zhi);
if(r>mid) updata(rt<<|,mid+,R,l,r,zhi);
} int query(int rt,int L,int R,int pos) {
if(L==R) return lazy[rt];//单点查
pushdown(rt);
int mid=(L+R)>>;
if(pos<=mid) query(rt<<,L,mid,pos);
else query(rt<<|,mid+,R,pos);
} int curr=;
int main() {
for(scanf("%d",&_);_;_--) {
printf("Case #%d:\n",curr++);
cur=;
mem(boss,);
mem(vis,);
scanf("%d",&n);
int u,v;
rep(i,,n) {//存关系
scanf("%d%d",&u,&v);
boss[v].push_back(u);
vis[u]=;
}
rep(i,,n+) {//找到根
if(!vis[i]) {
dfs(i);
break;
}
}
build(,,cur);//建树
scanf("%d",&m);
char s[];
int pos,zhi;
while(m--) {
scanf("%s",s);
if(s[]=='T') {
scanf("%d%d",&pos,&zhi);
updata(,,cur,st[pos],ed[pos],zhi);//区间st[pos]-ed[pos]是pos的员工
} else {
scanf("%d",&pos);
printf("%d\n",query(,,cur,st[pos]));//查pos的任务(ed[pos]就不是了)
}
}
}
}
最新文章
- Root--超级用户
- 简单学会.net remoting
- Android基于mAppWidget实现手绘地图(十)–在放大前后执行一些操作
- USACO八皇后
- CSS继承总结
- dt.jar设计时rt.jar运行时
- STL 源码分析《2》----nth_element() 使用与源码分析
- Linux中的15个‘echo’ 命令实例
- 【h5-egret】深入浅出对象池
- 【转】Xcode7真机调试iOS应用程序
- Win7 64位下配置Qt5.3和Wincap
- JSP(二)
- Sql 字符串操作类COALESCE
- 项目有叉号, 但是没有代码错误的时候, 是JDK版本的问题
- sizeof 与 strlen
- dp
- netsh &; winsock &; 对前端的影响
- Linux下栈溢出导致的core dump
- 微信开发之使用java获取签名signature(贴源码,附工程)
- 2019-04-15 Python之利用matplotlib和numpy的简单绘图