bzoj 4448 [Scoi2015]情报传递 (树链剖分+主席树)

时间:2021-12-04 22:32:31

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4448

题面:

Description

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络*有n名情报员。每名情报员口J-能有
若T名(可能没有)下线,除1名大头日外其余n-1名情报员有且仅有1名上线。奈特公司纪律森严,每
名情报员只能与自己的上、下线联系,同时,情报网络中仟意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务:
1.搜集情报:指派T号情报员搜集情报
2.传递情报:将一条情报从X号情报员传递给Y号情报员
情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为0;-旦某个情报员开
始搜集情报,他的危险值就会持续增加,每天增加1点危险值(开始搜集情报的当天危险值仍为0,第2天
危险值为1,第3天危险值为2,以此类推)。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全,每条情报都有一个风险控制值C。余特公司认为,参与传递这条情
报的所有情报员中,危险值大于C的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每
个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

Input

第1行包含1个正整数n,表示情报员个数。
笫2行包含n个非负整数,其中第i个整数Pi表示i号情报员上线的编号。特别地,若Pi=0,表示i号
情报员是大头目。
第3行包含1个正整数q,表示奈特公司将派发q个任务(每天一个)。
随后q行,依次描述q个任务。
每行首先有1个正整数k。若k=1,表示任务是传递情报,随后有3个正整数Xi、Yi、Ci,依次表示传递
情报的起点、终点和风险控制值;若k=2,表示任务是搜集情报,随后有1个正整数Ti,表示搜集情报的
情报员编号。

Output

对于每个传递情报任务输出一行,应包含两个整数,分别是参与传递情报的情报员个数和对该条情报构成威胁的情报员个数。
输出的行数应等于传递情报任务的个数,每行仅包含两个整数,用一个空格隔开。输出不应包含多余的空行和空格。

Sample Input

7
0 1 1 2 2 3 3
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3

Sample Output

5 0
5 2
5 1

HINT

对于3个传递情报任务,都是经过5名情报员,分别是4号、2号、1号、3号和7号。其中,对于第1个
任务,所有情报员(危险值为0)都不对情报构成威胁;对于第2个任务,有2名情报员对情报构成威胁,
分别是1号情报员(危险值为3)和4号情报员(危险值为2),7号情报员(危险值为1)并不构成威胁;
对于第3个任务,只有1名情报员对情报构成威胁。
n< = 2×10^5,Q< = 2×105,0< Pi,C!< = N, 1< = Ti,Xi,Yi< = n
思路:
这道题题意很好理解,就不说了,,
我们可以将k = 2的操作全部离线处理掉,对于k = 1的操作我们需要输出两个值:第一个值:两点间经过多少个点。。。这个树剖剖完后树就变成了一段区间,要求【x,y】区间的值
我们可以用【1,x】区间加上【1,y】区间减去两倍的【1,min(x,y)】区间再+1就好了,,如果看不懂可以去画下图就好了;
求第二个值我们只要在链(x,y)上找到所有 小于等于 i - ci - 1 的值就好了,这里用主席树区间查询下就好了。
写法:先用树链剖分将这棵树变成线性结构再用主席树处理下就好了。
 
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 2e5+;
const int Max = 5e6+;
struct node{
int to,next;
}e[M<<];
int head[M];
int dep[M],fa[M],siz[M],son[M],top[M],tid[M],rk[M],cnt,cnt1;
int ls[Max],rs[Max],sum[Max],root[Max],idx,n,q,t[M];
void add(int u,int v){
e[++cnt1].to = v; e[cnt1].next = head[u];head[u] = cnt1;
} void dfs1(int u,int faz,int deep){
dep[u] = deep;
fa[u] = faz;
siz[u] = ;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v != fa[u]){
dfs1(v,u,deep+);
siz[u] += siz[v];
if(son[u] == -||siz[v] > siz[son[u]])
son[u] = v;
}
}
} void dfs2(int u,int t){
top[u] = t;
tid[u] = cnt;
rk[cnt] = u;
cnt++;
if(son[u] == -) return ;
dfs2(son[u],t);
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v != son[u]&&v != fa[u])
dfs2(v,v);
}
} void update(int old,int &k,int l,int r,int p){
k = ++idx;
ls[k] = ls[old]; rs[k] = rs[old]; sum[k] = sum[old] + ;
if(l == r) return ;
mid;
if(p <= m) update(ls[old],ls[k],l,m,p);
else update(rs[old],rs[k],m+,r,p);
} int query(int L,int R,int l,int r,int p){
L = root[L - ], R = root[R];
int ret = ;
while(l != r){
mid;
if(p <= m) L = ls[L] ,R = ls[R], r = m;
else ret += sum[ls[R]] - sum[ls[L]],L = rs[L],R = rs[R],l = m+;
}
if(p >= l) ret += sum[R] - sum[L];
return ret;
} int solve(int x,int y,int p){
int ans = ; int fx = top[x],fy = top[y];
int tmp = dep[x] + dep[y];
while(fx != fy){
if(dep[fx] < dep[fy]) swap(x,y),swap(fx,fy);
ans += query(tid[fx],tid[x],,q,p);
x = fa[fx]; fx = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
ans += query(tid[x],tid[y],,q,p);
cout<<tmp - *dep[x] + <<" "<<ans<<endl;
}
int x,k,w,u[M],v[M],c[M];
int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
memset(son,-,sizeof(son));
cin>>n;
for(int i = ;i <= n;i ++){
cin>>x; add(x,i);
}
dfs1(,-,); dfs2(,);
cin>>q;
memset(t,q,sizeof(t));
int cnt2 = ;
for(int i = ;i <= n;i ++) t[i] = q;
for(int i = ;i <= q;i ++){
cin>>k;
if(k == ){
cin>>u[cnt2]>>v[cnt2]>>w;
c[cnt2++] = i - w - ;
}
else
cin>>x,t[x] = i;
}
for(int i = ;i <= n;i ++)
update(root[i-],root[i],,q,t[rk[i]]);
for(int i = ;i < cnt2;i ++)
solve(u[i],v[i],c[i]);
}

bzoj 4448 [Scoi2015]情报传递 (树链剖分+主席树)的更多相关文章

  1. dfs序&plus;主席树 或者 树链剖分&plus;主席树(没写) 或者 线段树套线段树 或者 线段树套splay 或者 线段树套树状数组 bzoj 4448

    4448: [Scoi2015]情报传递 Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 588  Solved: 308[Submit][Status ...

  2. BZOJ 4448&colon; &lbrack;Scoi2015&rsqb;情报传递 树链剖分 主席树

    4448: [Scoi2015]情报传递 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=4448 Description 奈特公司是一个巨 ...

  3. Codechef FIBTREE 树链剖分 主席树 LCA 二次剩余 快速幂

    原文链接https://www.cnblogs.com/zhouzhendong/p/CC-FIBTREE.html 题目传送门 - CC-FIBTREE 题意 给定一个有 $n$ 个节点,初始点权都 ...

  4. BZOJ1146 &lbrack;CTSC2008&rsqb;网络管理Network 树链剖分 主席树 树状数组

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1146 题意概括 在一棵树上,每一个点一个权值. 有两种操作: 1.单点修改 2.询问两点之间的树链 ...

  5. &lbrack;GDOI2016&rsqb;&lbrack;树链剖分&plus;主席树&rsqb;疯狂动物城

    题面 Description Nick 是只在动物城以坑蒙拐骗为生的狐狸,儿时受到偏见的伤害,放弃了自己的理想.他被兔子 Judy 设下圈套,*与她合作查案,而卷入意想不到的阴谋,历尽艰险后成为搭档 ...

  6. HDU 5111 Alexandra and Two Trees 树链剖分 &plus; 主席树

    题意: 给出两棵树,每棵树的节点都有一个权值. 同一棵树上的节点的权值互不相同,不同树上节点的权值可以相同. 要求回答如下询问: \(u_1 \, v_1 \, u_2 \, v_2\):询问第一棵树 ...

  7. 5&period;15 牛客挑战赛40 E&Tab;小V和gcd树 树链剖分 主席树 树状数组 根号分治

    LINK:小V和gcd树 时限是8s 所以当时好多nq的暴力都能跑过. 考虑每次询问暴力 跳父亲 这样是nq的 4e8左右 随便过. 不过每次跳到某个点的时候需要得到边权 如果直接暴力gcd的话 nq ...

  8. BZOJ3531 SDOI2014 旅行 - 树链剖分&comma;主席树

    题意:给定一棵树,树上每个点有权值和类型.支持:修改某个点的类型:修改某个点的权值:询问某条链上某个类型的点的和/最大值.点数/类型数/询问数<=100000. 分析: 树链剖分,对每个类型的点 ...

  9. BZOJ4012 HNOI2015开店(树链剖分&plus;主席树)

    考虑这样一个问题:一棵树初始全是白点,有两种操作:把一个点染黑:询问某点到所有黑点的距离之和. 注意到树上两点x和y的距离为depth[x]+depth[y]-depth[lca(x,y)]*2.要求 ...

随机推荐

  1. servlet 访问流程

  2. 8、面向对象以及winform的简单运用(事件与winform入门)

    事件 Visual studio中对可视化窗体控件的事件处理机理: 所有的.NET Framework可视化窗体控件的预定义事件,都会某一对应的“事件名+Handler”委托类型的变量.与此事件相关的 ...

  3. CSS3- px、em、rem区别介绍

    PX px像素(Pixel).相对长度单位.像素px是相对于显示器屏幕分辨率而言的. PX特点 1. IE无法调整那些使用px作为单位的字体大小: 2. 国外的大部分网站能够调整的原因在于其使用了em ...

  4. HDU1068&sol;POJ1466&lowbar;Girls and Boys&lpar;二分图&sol;最大独立集&equals;N-最大匹配&rpar;

    解题报告 http://blog.csdn.net/juncoder/article/details/38160591 题目传送门(POJ) 题目传送门(HDU) 题意: 求满足条件的最大集合:集合内 ...

  5. 【PHP】最详细PHP从入门到精通(三)——PHP中的数组

     PHP从入门到精通 之PHP中的数组 各位开发者朋友大家好,链接上次更新,我们PHP的学习也更深了一层,本次博主给大家带来PHP数组的数组实例详解的相关资料.数组分为数组数值数值,关联数组,多维数组 ...

  6. 区分舍入函数fix&sol;round&sol;ceil&sol;floor

    1)fix(n)的意义是取小于n的整数(是向零点舍入的意思是往零的方向上靠),这是一类应用在整数取值上的函数,就如同以前我们所研究的求整问题: 例如:fix(pi)=3 ; fix(3.5)=3;  ...

  7. vertx&period;io 与nodejs 一个简单的性能比较

    vertx.io 与node 都是可以进行js运行的一个引擎,但是vertx 支持的语言相对于node 多,可以查看官网.今天下网上查询相关的信息 时来了解到vertx.io 性能比node 好,于是 ...

  8. Linux服务-搭建Nginx

    任务目标:二进制安装nginx包,作为web服务修改配置文件,让配置生效,验证配置 首先使用yum 来安装 nginx 服务,基于epel-release平台的nginx需要epel的支持,所以要先安 ...

  9. SQL点点滴滴&lowbar;查询类型和索引-转载

    当您考虑是否要对列创建索引时, 请估计在查询中使用列的方式, 下表介绍了索引对其有用的查询类型. 表中的示例基于 AdventureWorks2008R2 示例数据库, 在 SQL Server Ma ...

  10. Windows下通过Composer安装Yii2

    安装好大于5.4或更高版本的PHP环境并开启openssl扩展.如果是Apache服务器,加载Apache的mod_ssl模块. 下载Composer并安装. 开始->运行[或者WIN+R]-& ...