没有合适的资源?快使用搜索试试~ 我知道了~
NOIP树链剖分习题讲解报告
需积分: 15 0 下载量 2 浏览量
2022-11-01
16:35:34
上传
评论
收藏 40KB DOCX 举报
温馨提示
试读
35页
P2590 [ZJOI2008]树的统计 P3384 【模板】轻重链剖分/树链剖分 P3950 部落冲突 P4092 [HEOI2016/TJOI2016]树 P2146 [NOI2015] 软件包管理器
资源推荐
资源详情
资源评论
第 1 页 /共 35 页
树链剖分练习题讲解
P2590 [ZJOI2008]树的统计 时间限制 1.00s 内存限制 125.00MB
题目描述
一棵树上有 n 个节点,编号分别为 1 到 n,每个节点都有一个权值 w。
我们将以下面的形式来要求你对这棵树完成一些操作:
I. CHANGE u t : 把结点 u 的权值改为 t。
II. QMAX u v: 询问从点 u 到点 v 的路径上的节点的最大权值。
III. QSUM u v: 询问从点 u 到点 v 的路径上的节点的权值和。
注意:从点 u 到点 v 的路径上的节点包括 u 和 v 本身。
输入格式
输入文件的第一行为一个整数 n,表示节点的个数。
接下来 n-1 行,每行 2 个整数 a 和 b,表示节点 a 和节点 b 之间有一条边相
连。
接下来一行 n 个整数,第 i 个整数 wi 表示节点 ii 的权值。
接下来 1 行,为一个整数 q,表示操作的总数。
接下来 q 行,每行一个操作,以 CHANGE u t 或者 QMAX u v 或者 QSUM u v
的形式给出。
输出格式
对于每个 QMAX 或者 QSUM 的操作,每行输出一个整数表示要求输出的结
果。
输入输出样例
输入 #1
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
第 2 页 /共 35 页
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
输出 #1
4
1
2
2
10
6
5
6
5
16
说明/提示
对于 100% 的数据,保证
1
≤
n
≤
3
×
10
4
,
0
≤
q
≤
2
×
10
5
。
中途操作中保证每个节点的权值 w 在
―
3
×
10
4
到
3
×
10
4
之间。
P3384 【模板】轻重链剖分/树链剖分 时间限制 1.00s 内存限制 125.00MB
题目描述
如题,已知一棵包含 N 个结点的树(连通且无环),每个节点上包含一个数
值,需要支持以下操作:
1 x y z,表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
第 3 页 /共 35 页
2 x y,表示求树从 x 到 y 结点最短路径上所有节点的值之和。
3 x z,表示将以 x 为根节点的子树内所有节点值都加上 z。
4 x 表示求以 x 为根节点的子树内所有节点值之和
输入格式
第一行包含 4 个正整数 N,M,R,P,分别表示树的结点个数、操作个数、根节
点序号和取模数(即所有的输出结果均对此取模)。
接下来一行包含 N 个非负整数,分别依次表示各个节点上初始的数值。
接下来 N-1 行每行包含两个整数 x,y,表示点 x 和点 y 之间连有一条边(保证
无环且连通)。
接下来 M 行每行包含若干个正整数,每行表示一个操作。
输出格式
输出包含若干行,分别依次表示每个操作 2 或操作 4 所得的结果(对 P 取
模)。
输入输出样例
输入 #1
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
输出 #1
2
21
第 4 页 /共 35 页
说明/提示
【数据规模】
对于 30% 的数据: 1≤N≤10,1≤M≤10;
对于 70% 的数据:
1
≤
N
≤
10
3
,
1
≤
M
≤
10
3
;
对于 100% 的数据:
1
≤
N
≤
10
5
,1
≤
M
≤
10
5
,1
≤
R
≤
N,1
≤
P
≤
2
31
―
1
。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <map>
#include <queue>
#define ri register int
#define ll long long
using std::swap;
const int maxn=100005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
struct Edge{
int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
第 5 页 /共 35 页
inline void add_edge(int f,int t){
edge[++num_edge].ne=h[f];
edge[num_edge].to=t;
h[f]=num_edge;
return ;
}
int n,m,r,p;
int
cnt=0,dep[maxn],fa[maxn],son[maxn],top[maxn],dfn[maxn],rnk[maxn],size[maxn];
void dfs_1(int now){
int v;size[now]=1;
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(v==fa[now])continue;
fa[v]=now,dep[v]=dep[now]+1;
dfs_1(v);
size[now]+=size[v];
if(!son[now]||size[son[now]]<size[v])son[now]=v;
}
return ;
}
void dfs_2(int now,int t){
int v;top[now]=t,dfn[now]=++cnt,rnk[cnt]=now;
if(!son[now])return ;
dfs_2(son[now],t);
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(v==fa[now]||v==son[now])continue;
dfs_2(v,v);
}
剩余34页未读,继续阅读
资源评论
smghj
- 粉丝: 1
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功