题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4448
题面:
Description
Input
Output
Sample Input
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 2
5 1
HINT
#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]情报传递 (树链剖分+主席树)的更多相关文章
-
dfs序+主席树 或者 树链剖分+主席树(没写) 或者 线段树套线段树 或者 线段树套splay 或者 线段树套树状数组 bzoj 4448
4448: [Scoi2015]情报传递 Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 588 Solved: 308[Submit][Status ...
-
BZOJ 4448: [Scoi2015]情报传递 树链剖分 主席树
4448: [Scoi2015]情报传递 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=4448 Description 奈特公司是一个巨 ...
-
Codechef FIBTREE 树链剖分 主席树 LCA 二次剩余 快速幂
原文链接https://www.cnblogs.com/zhouzhendong/p/CC-FIBTREE.html 题目传送门 - CC-FIBTREE 题意 给定一个有 $n$ 个节点,初始点权都 ...
-
BZOJ1146 [CTSC2008]网络管理Network 树链剖分 主席树 树状数组
欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1146 题意概括 在一棵树上,每一个点一个权值. 有两种操作: 1.单点修改 2.询问两点之间的树链 ...
-
[GDOI2016][树链剖分+主席树]疯狂动物城
题面 Description Nick 是只在动物城以坑蒙拐骗为生的狐狸,儿时受到偏见的伤害,放弃了自己的理想.他被兔子 Judy 设下圈套,*与她合作查案,而卷入意想不到的阴谋,历尽艰险后成为搭档 ...
-
HDU 5111 Alexandra and Two Trees 树链剖分 + 主席树
题意: 给出两棵树,每棵树的节点都有一个权值. 同一棵树上的节点的权值互不相同,不同树上节点的权值可以相同. 要求回答如下询问: \(u_1 \, v_1 \, u_2 \, v_2\):询问第一棵树 ...
-
5.15 牛客挑战赛40 E	小V和gcd树 树链剖分 主席树 树状数组 根号分治
LINK:小V和gcd树 时限是8s 所以当时好多nq的暴力都能跑过. 考虑每次询问暴力 跳父亲 这样是nq的 4e8左右 随便过. 不过每次跳到某个点的时候需要得到边权 如果直接暴力gcd的话 nq ...
-
BZOJ3531 SDOI2014 旅行 - 树链剖分,主席树
题意:给定一棵树,树上每个点有权值和类型.支持:修改某个点的类型:修改某个点的权值:询问某条链上某个类型的点的和/最大值.点数/类型数/询问数<=100000. 分析: 树链剖分,对每个类型的点 ...
-
BZOJ4012 HNOI2015开店(树链剖分+主席树)
考虑这样一个问题:一棵树初始全是白点,有两种操作:把一个点染黑:询问某点到所有黑点的距离之和. 注意到树上两点x和y的距离为depth[x]+depth[y]-depth[lca(x,y)]*2.要求 ...
随机推荐
- servlet 访问流程
-
8、面向对象以及winform的简单运用(事件与winform入门)
事件 Visual studio中对可视化窗体控件的事件处理机理: 所有的.NET Framework可视化窗体控件的预定义事件,都会某一对应的“事件名+Handler”委托类型的变量.与此事件相关的 ...
-
CSS3- px、em、rem区别介绍
PX px像素(Pixel).相对长度单位.像素px是相对于显示器屏幕分辨率而言的. PX特点 1. IE无法调整那些使用px作为单位的字体大小: 2. 国外的大部分网站能够调整的原因在于其使用了em ...
-
HDU1068/POJ1466_Girls and Boys(二分图/最大独立集=N-最大匹配)
解题报告 http://blog.csdn.net/juncoder/article/details/38160591 题目传送门(POJ) 题目传送门(HDU) 题意: 求满足条件的最大集合:集合内 ...
-
【PHP】最详细PHP从入门到精通(三)——PHP中的数组
PHP从入门到精通 之PHP中的数组 各位开发者朋友大家好,链接上次更新,我们PHP的学习也更深了一层,本次博主给大家带来PHP数组的数组实例详解的相关资料.数组分为数组数值数值,关联数组,多维数组 ...
-
区分舍入函数fix/round/ceil/floor
1)fix(n)的意义是取小于n的整数(是向零点舍入的意思是往零的方向上靠),这是一类应用在整数取值上的函数,就如同以前我们所研究的求整问题: 例如:fix(pi)=3 ; fix(3.5)=3; ...
-
vertx.io 与nodejs 一个简单的性能比较
vertx.io 与node 都是可以进行js运行的一个引擎,但是vertx 支持的语言相对于node 多,可以查看官网.今天下网上查询相关的信息 时来了解到vertx.io 性能比node 好,于是 ...
-
Linux服务-搭建Nginx
任务目标:二进制安装nginx包,作为web服务修改配置文件,让配置生效,验证配置 首先使用yum 来安装 nginx 服务,基于epel-release平台的nginx需要epel的支持,所以要先安 ...
-
SQL点点滴滴_查询类型和索引-转载
当您考虑是否要对列创建索引时, 请估计在查询中使用列的方式, 下表介绍了索引对其有用的查询类型. 表中的示例基于 AdventureWorks2008R2 示例数据库, 在 SQL Server Ma ...
-
Windows下通过Composer安装Yii2
安装好大于5.4或更高版本的PHP环境并开启openssl扩展.如果是Apache服务器,加载Apache的mod_ssl模块. 下载Composer并安装. 开始->运行[或者WIN+R]-& ...