树链剖分
树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度 需要处理的问题：
- 将树从x到y结点最短路径上所有节点的值都加上z
- 求树从x到y结点最短路径上所有节点的值之和
- 将以x为根节点的子树内所有节点值都加上z
- 求以x为根节点的子树内所有节点值之和
树链剖分的策略是将这些点按某种方式组织起来，剖分为若干条链，每条链就相当于一个序列。这样，操作的路径可以拆分为某几条链，也就是若干个完整序列或是某个序列上的一段区间，此时可以用线段树等处理序列上区间新操作的数据结构去解决问题。树链剖分的核心是如何恰当的将树剖分为若干条链，当链的划分方式确定时，只需要将他们看作一个个序列，将所有的序列按照顺序拼接起来，每条链就形成了一个区间，而序列上的区间问题使我们擅长解决的.
- fa[u]:u在树中的父亲
- dep[u]:u节点的深度
- size[u]:u的子树节点数(子树大小)
- son[u]:u的重儿子
- top[u]:u所在重链的顶部节点
- id[x]:新的编号
- wt[x]:新编号的点权
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
#include <bits/stdc++.h>//此题为点建树
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int N = 2e5 + 10;
int sum[N << 2], lazy[N << 2]; //线段树求和
int n, m, r, mod; //节点数，操作数，根节点，模数
int first[N], tot; //邻接表
//分别为:重儿子，每个节点新编号，父亲，编号，深度，子树个数，所在重链的顶部
int son[N], id[N], fa[N], cnt, dep[N], siz[N], top[N];
int w[N], wt[N]; //初始点权,新编号点权
int res = 0; //查询答案
struct edge
{
int v, next;
} e[N];
void add_edge(int u, int v)
{
e[tot].v = v;
e[tot].next = first[u];
first[u] = tot++;
}
void init()
{
mem(first, -1);
tot = 0;
cnt = 0;
}
int pushup(int rt)
{
sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
}
void pushdown(int rt, int m) //下放lazy标记
{
if (lazy[rt])
{
lazy[rt << 1] += lazy[rt]; //给左儿子下放lazy
lazy[rt << 1 | 1] += lazy[rt]; //给右儿子下放lazy
sum[rt << 1] += lazy[rt] * (m - (m >> 1)); //更新sum
sum[rt << 1] %= mod;
sum[rt << 1 | 1] += lazy[rt] * (m >> 1);
sum[rt << 1 | 1] %= mod;
lazy[rt] = 0;
}
}
void build(int l, int r, int rt)
{
lazy[rt] = 0;
if (l == r)
{
sum[rt] = wt[l]; //新的编号点权
sum[rt] %= mod;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
if (L <= l && r <= R)
{
lazy[rt] += c;
sum[rt] += c * (r - l + 1);
sum[rt] %= mod;
return;
}
pushdown(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m)
update(L, R, c, lson);
if (R > m)
update(L, R, c, rson);
pushup(rt);
}
void query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
{
res += sum[rt];
res %= mod;
return;
}
pushdown(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m)
query(L, R, lson);
if (R > m)
query(L, R, rson);
}
//----------------------------------------------------------------
//处理出fa[],dep[],siz[],son[]
void dfs1(int u, int f, int deep)
{
dep[u] = deep; //标记深度
fa[u] = f; //标记节点的父亲
siz[u] = 1; //记录每个节点子树大小
int maxson = -1; //记录重儿子数量
for (int i = first[u]; ~i; i = e[i].next)
{
int v = e[i].v;
if (v == f)
continue;
dfs1(v, u, deep + 1);
siz[u] += siz[v];
if (siz[v] > maxson) //儿子里最多siz就是重儿子
{
son[u] = v; //标记u的重儿子为v
maxson = siz[v];
}
}
}
//处理出top[],wt[],id[]
void dfs2(int u, int topf)
{
id[u] = ++cnt; //每个节点的新编号
wt[cnt] = w[u]; //新编号的对应权值
top[u] = topf; //标记每个重链的顶端
if (!son[u]) //没有儿子时返回
return;
dfs2(son[u], topf); //搜索下一个重儿子
for (int i = first[u]; ~i; i = e[i].next)
{
int v = e[i].v;
if (v == fa[u] || v == son[u]) //处理轻儿子
continue;
dfs2(v, v); //每一个轻儿子都有一个从自己开始的链
}
}
void updrange(int x, int y, int k)
{
k %= mod;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) //使x深度较大
swap(x, y);
update(id[top[x]], id[x], k, 1, n, 1);
x = fa[top[x]];
}
if (dep[x] > dep[y]) //使x深度较小
swap(x, y);
update(id[x], id[y], k, 1, n, 1);
}
int qrange(int x, int y)
{
int ans = 0;
while (top[x] != top[y]) //当两个点不在同一条链上
{
if (dep[top[x]] < dep[top[y]]) //使x深度较大
swap(x, y);
res = 0;
query(id[top[x]], id[x], 1, n, 1);
//ans加上x点到x所在链顶端这一段区间的点权和
ans += res;
ans %= mod;
x = fa[top[x]]; //x跳到x所在链顶端的这个点的上面一个点
}
//当两个点处于同一条链
if (dep[x] > dep[y]) //使x深度较小
swap(x, y);
res = 0;
query(id[x], id[y], 1, n, 1);
ans += res;
return ans % mod;
}
void upson(int x, int k)
{
update(id[x], id[x] + siz[x] - 1, k, 1, n, 1); //子树区间右端点为id[x]+siz[x]-1
}
int qson(int x)
{
res = 0;
query(id[x], id[x] + siz[x] - 1, 1, n, 1);
return res;
}
int main()
{
// freopen("in.txt", "r", stdin);
int u, v;
scanf("%d%d%d%d", &n, &m, &r, &mod);
init();
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i <= n - 1; i++)
{
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs1(r, 0, 1);
dfs2(r, r);
build(1, n, 1); //用新点权建立线段树
while (m--)
{
int op, x, y, z;
scanf("%d", &op);
if (op == 1)
{
scanf("%d%d%d", &x, &y, &z);
updrange(x, y, z);
}
else if (op == 2)
{
scanf("%d%d", &x, &y);
printf("%d\n", qrange(x, y));
}
else if (op == 3)
{
scanf("%d%d", &x, &z);
upson(x, z);
}
else if (op == 4)
{
scanf("%d", &x);
printf("%d\n", qson(x));
}
}
return 0;
}
边建树 SPOJ QTREE - Query on a tree(树链剖分，以边建树）
给你一棵具有n个节点的树，每条边都有一个权值，题目定义了两种操作。
- change x y:把第x条边的权值改为y
- query x y:询问从点x到点y路径上的最大的边的权值
以前做树链剖分都是点有取值，这一题是边有权值，我们在处理的时候，对于每一条边的权值，可以把这个权值赋值给比深度比较大的点上。这样就可以把边权改为点权，更容易维护.
因为是多组数据，注意初始化
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 5e4 + 10;
const int inf=0x3f3f3f3f;
int MAX[N<<2];
int first[N],tot,n;
int w[N],cnt;
int fa[N],siz[N],dep[N],son[N],id[N],top[N];
struct edge
{
int u,v,w,next;
} e[N];
void add_edge(int u,int v,int w)
{
e[tot].u=u,e[tot].v=v,e[tot].w=w;
e[tot].next=first[u];
first[u]=tot++;
}
void init()
{
mem(first,-1);
tot=0;
cnt=0;
}
void pushup(int rt)
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
MAX[rt]=w[l];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,int c,int l,int r,int rt)
{
if(l==r)
{
MAX[rt]=c;
return;
}
int m=(l+r)>>1;
if(p<=m) update(p,c,lson);
else update(p,c,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return MAX[rt];
int m=(l+r)>>1;
int ans=0;
if(L<=m) ans=max(ans,query(L,R,lson));
if(R>m) ans=max(ans,query(L,R,rson));
return ans;
}
void dfs1(int u,int f,int deep)
{
fa[u]=f;
siz[u]=1;
dep[u]=deep;
son[u]=0;//很重要
int maxson=-1;
for(int i=first[u]; ~i; i=e[i].next)
{
int v=e[i].v;
if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson)
{
son[u]=v;
maxson=siz[v];
}
}
}
void dfs2(int u,int topf)
{
top[u]=topf;
id[u]=++cnt;
if(!son[u])
return;
dfs2(son[u],topf);
for(int i=first[u]; ~i; i=e[i].next)
{
int v=e[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int qmax(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans=max(ans,query(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ans=max(ans,query(id[son[x]],id[y],1,n,1));//不包含当前节点，所以是son[x]
return ans;
}
void change(int x,int k)
{
x--;
update(id[e[2*x].u],k,1,n,1);//因为是双向边，所以是e[2*x].u
}
int main()
{
int t,a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(int i=1; i<=n-1; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i = 0; i < tot; i += 2)
{
if (dep[e[i].u] < dep[e[i].v])
swap(e[i].u, e[i].v);
w[id[e[i].u]] = e[i].w;
}
build(1,n,1);
char s[10];
while(scanf("%s",s)&&s[0]!='D')
{
scanf("%d%d",&a,&b);
if(s[0]=='Q')
printf("%d\n",qmax(a,b));
else if(s[0]=='C')
change(a,b);
}
}
return 0;
}
这道题的前置题目是:SPOJ QTREE - Query on a tree(树链剖分，以边建树）
其中的query操作和change这两题操作是一样的本题中，主要是加了一个negate x y的操作，把x到y路径上的所有边都变成它的相反数。我们需要同时记录最大值和最小值，lazy数组进行标记当前节点有没有需要更新，如果需要就把当前节点的最大最小值变成相反数(最大值变成相反数成了最小值，最小值变成相反数变成了最大值)在线段树操作的时候，最大值初始值赋成负无穷
const int N = 2e5 + 10;
const int inf=0x3f3f3f3f;
int MAX[N<<2],MIN[N<<2],flag[N<<2];
int first[N],tot,n;
int w[N],cnt;
int fa[N],siz[N],dep[N],son[N],id[N],top[N];
struct edge
{
int u,v,w,next;
} e[N];
void add_edge(int u,int v,int w)
{
e[tot].u=u,e[tot].v=v,e[tot].w=w;
e[tot].next=first[u];
first[u]=tot++;
}
void init()
{
mem(first,-1);
tot=0;
cnt=0;
}
void pushup(int rt)
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
}
void pushdown(int rt)
{
if(flag[rt])//此点需要操作的时候
{
MAX[rt<<1]*=-1;
MIN[rt<<1]*=-1;
swap(MAX[rt<<1],MIN[rt<<1]);
MAX[rt<<1|1]*=-1;
MIN[rt<<1|1]*=-1;
swap(MAX[rt<<1|1],MIN[rt<<1|1]);
flag[rt<<1]^=1;
flag[rt<<1|1]^=1;
flag[rt]=0;
}
}
void build(int l,int r,int rt)
{
flag[rt]=0;
if(l==r)
{
MAX[rt]=MIN[rt]=w[l];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,int c,int l,int r,int rt)
{
if(l==r)
{
MAX[rt]=MIN[rt]=c;
flag[rt]=0;
return;
}
int m=(l+r)>>1;
pushdown(rt);
if(p<=m) update(p,c,lson);
else update(p,c,rson);
pushup(rt);
}
void ne_update(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
MAX[rt]*=-1;
MIN[rt]*=-1;
swap(MAX[rt],MIN[rt]);
flag[rt]^=1;
return;
}
pushdown(rt);
int m=(l+r)>>1;
if(L<=m) ne_update(L,R,lson);
if(R>m) ne_update(L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return MAX[rt];
int m=(l+r)>>1;
pushdown(rt);
int ans=-inf;
if(L<=m) ans=max(ans,query(L,R,lson));
if(R>m) ans=max(ans,query(L,R,rson));
return ans;
}
void dfs1(int u,int f,int deep)
{略}
void dfs2(int u,int topf)
{略}
int qmax(int x,int y)
{
int ans=-inf;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans=max(ans,query(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ans=max(ans,query(id[son[x]],id[y],1,n,1));//不包含当前节点，所以是son[x]
return ans;
}
void change(int x,int k)
{
x--;
update(id[e[2*x].u],k,1,n,1);//因为是双向边，所以是e[2*x].u
}
void ngate(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ne_update(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ne_update(id[son[x]],id[y],1,n,1);
}
int main()
{
int t,a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(int i=1; i<=n-1; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i = 0; i < tot; i += 2)
{
if (dep[e[i].u] < dep[e[i].v])
swap(e[i].u, e[i].v);
w[id[e[i].u]] = e[i].w;
}
build(1,n,1);
char s[10];
while(scanf("%s",s)&&s[0]!='D')
{
scanf("%d%d",&a,&b);
if(s[0]=='Q')
printf("%d\n",qmax(a,b));
else if(s[0]=='C')
change(a,b);
else if(s[0]=='N')
ngate(a,b);
}
}
return 0;
}