HDU3974 Assign the task —— dfs时间戳 + 线段树
题目链接:https://vjudge.net/problem/HDU-3974
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
题解:
1.可知:对一棵树进行dfs(前序遍历),并为每个结点分配一个时间戳,表明该结点是第几个被访问的结点。对于某一个结点(非叶子),它的所有子孙的遍历次序是紧跟着当前节点的。
2.根据时间戳dfn[u],把每个结点u映射到一维数组上。设le[u]为子树u开始访问的时间戳,可知le[u]=dfn[u];ri[u]为子树u结束访问的时间戳,可知ri[u]为结点u最后被访问的子孙的时间戳。所以结点u的作用域就是: [ le[u], ri[u] ]。因此,我们就可以用线段树的区间修改来进行维护了。
学习之处:
根据DFS的特性:对一棵树进行先序遍历,对于当前结点u,它的所有子孙的遍历次序是紧跟着当前节点的。
因此,我们可以根据时间戳,把一棵树映射到到一维数组上,且可以知道每棵子树的确切位置。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 5e4+; vector<int>g[MAXN];
int have_fa[MAXN];
int index, dfn[MAXN], le[MAXN], ri[MAXN];
int task[MAXN<<]; void dfs(int u)
{
dfn[u] = le[u] = ++index;
for(int i = ; i<g[u].size(); i++)
dfs(g[u][i]);
ri[u] = index;
} void push_down(int u)
{
if(task[u]!=-)
{
task[u*] = task[u*+] = task[u];
task[u] = -;
}
} void set_val(int u, int l, int r, int x, int y, int val)
{
if(x<=l && r<=y)
{
task[u] = val;
return;
} push_down(u);
int mid = (l+r)>>;
if(x<=mid) set_val(u*, l, mid, x, y, val);
if(y>=mid+) set_val(u*+, mid+, r, x, y, val);
} int query(int u, int l, int r, int x)
{
if(l==r) return task[u]; push_down(u);
int mid = (l+r)>>;
if(x<=mid) return query(u*, l, mid, x);
else return query(u*+, mid+, r, x);
} int main()
{
int n, m, T;
scanf("%d", &T);
for(int kase = ; kase<=T; kase++)
{
scanf("%d", &n);
for(int i = ; i<=n; i++)
g[i].clear(), have_fa[i] = ;
for(int i = ; i<n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
g[v].push_back(u);
have_fa[u] = ;
} index = ;
for(int i = ; i<=n; i++)
if(!have_fa[i])
dfs(i); scanf("%d", &m);
memset(task, -, sizeof(task));
printf("Case #%d:\n", kase);
for(int i = ; i<=m; i++)
{
char op[]; int x, y;
scanf("%s", op);
if(op[]=='T')
{
scanf("%d%d", &x, &y);
set_val(, , n, le[x], ri[x], y);
}
else
{
scanf("%d", &x);
printf("%d\n", query(, , n, dfn[x]));
}
}
}
}
最新文章
- 退出系统时跳出frame框架
- php-fpm启动
- Zabbix监控交换机设置
- 查看图片真正的格式,在不知道扩展名的情况下区分是jpeg还是bmp
- JAVA操作Excel时文字自适应单元格的宽度设置方法
- Hibernate中load与get的区别
- 无法从“const char *”转换为“char *”
- zimbra启用SMTP认证并绑定认证登录和发件人
- MVC.NET 发布后,部署到iis ,网站中的Bootstrap的字体图标不能正常显示
- 对于分支界限法的理解(补出门门票-week13,结对伙伴对我提的问题的答案)
- Spring Web工程web.xml零配置即使用Java Config + Annotation
- CentOS 安装 ceph 单机版(luminous版本)
- NDK开发入门终极教程
- LAMP环境快速搭建
- 一切为了落地,为什么要把PP.io设计成三个阶段!
- ExtJS初探:在项目中使用ExtJS
- 浏览器的cookie的值改成字典格式
- C# 多线程学习系列三之CLR线程池系列之ThreadPool
- WebLogic使用总结(四)——WebLogic部署Web应用
- Spring Boot 上传文件 获取项目根路径 物理地址 resttemplate上传文件
热门文章
- 【转】亿级Web系统搭建——单机到分布式集群
- python re 正则提取中文
- 前端接收到的json的属性的首字母会自动变成小写,解决办法如下
- springboot注释详解
- F - The Minimum Length
- Caused by: java.lang.IncompatibleClassChangeError: class org.springframework.scheduling.quartz.CronTriggerBean has interface org.quartz.CronTrigger as super class
- DRBD原理知识
- 纠结的链接——ln、ln -s、fs.symlink、require
- poj 1695 Magazine Delivery 记忆化搜索
- 再谈用java实现Smtp发送邮件之Socket编程