/*
节点的标号从1开始
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10000; //N为节点的个数
struct e{
int v;
e* nxt;
}es[N<<1], *fir[N];
struct node{
int ls, rs; //左右儿子的下标,为-1表示空
int l, r; //区间的左右标号
//数据域,根据不同的需要添加,数据的down和update和线段树的无异
int mid() { return (l + r) >> 1; }
}nodes[N<<1];
int n, en;
int que[N], par[N], dep[N], root[N], seg[N], st[N], ed[N], top[N], sons[N], id[N];
//que用于BFS,par记录父节点,dep记录节点的深度。 root[i]为链i的根节点,seg用于在链上建线段树,
//st[i],ed[i]分别为链i的左右端点,top[i]为链i的顶部的节点,sons[i]为节点i的儿子节点
//id[i]是节点i所属的链的标号,
int ln, cnt, tr; //ln是链的个数,cnt为节点的个数,tr是树的根节点
inline void add_e(int u, int v){
es[en].v = v;
es[en].nxt = fir[u];
fir[u] = &es[en++];
}
inline void newNode(int& id, int l, int r){
nodes[cnt].ls = nodes[cnt].rs = -1;
nodes[cnt].l = l;
nodes[cnt].r = r;
id = cnt++;
}
void build(int& id, int l, int r){ //在剖分出来的链上构建线段树
newNode(id, l, r);
if(l >= r){
//seg[l]为落在这个线段树节点上的原树中的节点
return ;
}
int mid = (l+r)>>1;
build(nodes[id].ls, l, mid);
build(nodes[id].rs, mid+1, r);
}
void initTree(){ //初始化剖分树
//确定父亲
int l, r, u, v, i;
e* cur;
l = r = 0;
que[r++] = tr;
par[tr] = -1;
dep[tr] = 0;
while(l != r){
u = que[l++];
int g = 1;
for(cur = fir[u]; cur; cur = cur->nxt){
if((v = cur->v) != par[u]){
que[r++] = v;
par[v] = u;
dep[v] = dep[u]+1;
}
}
}
//计算子树大小
for(i = 1; i <= n; i++){
sons[i] = 1;
id[i] = -1;
}
for(i = r-1; i >= 0; i--){
u = que[i];
if(par[u] >= 0){
sons[par[u]] += sons[u];
}
}
//剖分链
l = r = 0;
que[r++] = tr;
ln = cnt = 0;
while(l != r){
u = que[l++];
st[ln] = dep[u]; //用节点的深度作为线段树中区间的左右标号
top[ln] = u;
while(u >= 0){
id[u] = ln;
ed[ln] = dep[u];
seg[dep[u]] = u;
int best;
for(cur = fir[u], best=-1; cur; cur = cur->nxt){
if(id[v = cur->v] == -1){
if(best == -1 || (best >= 0 && sons[v] > sons[best])){
best = v;
}
}
}
if(best >= 0){
for(cur = fir[u]; cur; cur = cur->nxt){
if(id[v = cur->v] == -1 && best != v){
que[r++] = v;
}
}
}
u = best;
}
root[ln] = -1;
build(root[ln], st[ln], ed[ln]);
ln++;
}
}
void lqry(int& id, int ql, int qr){
if(id == -1) return ;
if(ql <= nodes[id].l && nodes[id].r <= qr){
return ;
}
if(nodes[id].l == nodes[id].r){
return ;
}
int mid = (nodes[id].l+nodes[id].r)>>1;
if(ql <= mid){
lqry(nodes[id].ls, ql, qr);
}
if(qr > mid){
lqry(nodes[id].rs, ql, qr);
}
}
void qry(int u, int v){ //查询u和v之间的最大值
while(id[u] != id[v]){
if(id[u] > id[v]){
swap(u, v);
}
int b = id[v];
lqry(root[b], st[b], dep[v]);
v = par[top[b]];
}
if(dep[u] > dep[v]){
swap(u, v);
}
lqry(root[id[u]], dep[u], dep[v]);
}
int main(){
return 0;
}
分享到:
相关推荐
#include #include #include #define N 30003 #define INF 2147483647 using namespace std; int n,f[N][20],dep[N],siz[N],son[N],top[N],tot,pos[N],w[N]; int Max[N*4],Sum[N*4];...vector <int> to[N];...
树链剖分,luoguP3384 【模板】重链剖分
P2590 [ZJOI2008]树的统计 P3384 【模板】轻重链剖分/树链剖分 P3950 部落冲突 P4092 [HEOI2016/TJOI2016]树 P2146 [NOI2015] 软件包管理器
ACM模版-->矩阵快速幂,搜索,树链剖分,线段树,动态规划,RMQ
3.10 线段树合并 . 3.11 树链剖分 3.12 李超线段树 . 3.14 左偏树 . 3.15 带修改区间第 k 小 . 3.16 Segment Be
树链剖分 52 平衡二叉树 56 Splay 56 数学 64 结论&&推论 64 快速乘法 65 逆元 66 [1, n]素数个数 66 pell方程 68 秦九韶算法 68 求π 69 黑科技 72 求某天是星期几 72 扩栈 73 JAVA 73 builtin函数 74
线段树,splay,lct,后缀数组,后缀自动机,树链剖分的简单易懂的c++模板
4.最小生成树 5.拓扑排序 6.差分约束 7.倍增求LCA 8.有向图的强联通分量 9.无向图的双联通分量 1.树状数组 2.线段树 3.树链剖分 4.平衡树
目录 SG打表: 1 树链剖分 3 树形dp 7 状态压缩dp 9 数论公式 (补充) 11 素数个数 16 最大团 20 SG打表://f[]:可以取走的石
包括树剖,线段树,splay,Treap,网络流,RMQ,数论函数求值,主席树,树状数组,LCA,CRT,BSGS,树套树等模板。(注:其中的两个cdq模板都没用的,整体二分写错了,其余模板可以自行测试。 p.s.有些可能与一些已...
树链剖分 树的点分治 树的边分治 图论 图的基本结构 强联通分量 无向图求桥 无向图求割点 二分图匹配 匈牙利算法 Hopcroft-Karp算法 二分图最优匹配 KM 算法 最小树形图 朱刘算法 最大密度子图 01分数规划 && 网络流...
树链剖分: with 线段树: String 后缀数组: Geo 凸包: 旋转卡壳: LeetCode 目前只打算做easy和medium中的大部分题目(有些恶心的模拟和锁题不写),偶尔看到拍个板子就能过的hard题也会顺手过一下 模板
1 字符串处理 5 1.1 KMP . . . . ....3.3 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.3.1 点权 . . . . . . . . . . . . . . . . . . . . . . ...
轻重链剖分 二次剩余 Pell方程 无向图最小割 长方体表面两点最短距离 墓地 KD Tree 极大团 动态最小生成树 Romberg NTT FWT DC3 图同构Hash 消圈 结论 弦图相关 各种公式,结论 积分表 List of Todo To be