Housewife Wind 【边权区间查询】
题意
说有一个由 N-1 条边连接起来的 N 点树形图，每条边有一个权值.某个acmer站在起点start【代码中记为P】，接下来 acmer 会有 M 次操作，操作呢有以下两种：
1 i w ：将第 i 条边的边权修改为 W
0 u ：打印从 start 到 u 点的边权和，并且更新start位置为 U
相关解释：
far[]：存储节点的父亲节点
dep[]：存储节点的深度值
s z[]：存储以节点为根的子树节点个数
son[]：保存重儿子
r k[]：保存当前DFS标号在树中所对应的节点
top[]：保存节点所在链的顶端节点，实质就是为LCA
i d[]：保存树中每个节点刨分之后的新编号（DFS的执行顺序）
DFS_init(1,0,1,0); /// 调用
void DFS_init(int u,int pre,int d,int w) /// 当前节点，前驱结点，深度，权值
{
dep[u] = d , far[u] = pre , sz[u] = 1 , val[u] = w ;/// sz[u]=1：子树包括根节点
for(int i=head[u];~i;i=e[i].nx){
int v = e[i].to ;
if(v==pre) continue ;
DFS_init(v,u,d+1,e[i].w); /// 回溯的时候更新 U 节点的信息
sz[u]+=sz[v]; /// 更新子树节点个数，准备刨分
if(sz[v]>sz[son[u]]) son[u] = v ; /// 更新重儿子
}
}
DFS(1,1);
void DFS(int u,int x) /// 当前节点，重链顶端
{
top[u] = x , id[u] = ++res , rk[res] = u ;/// id[] 记录DFS序，rk[] 记录DFS序对应节点
if(son[u]) DFS(son[u],x);/// 优先处里重儿子来保证重链上各节点的DFS序连续
for(int i=head[u];~i;i=e[i].nx){
int v = e[i].to ;
if(v!=son[u] && v!=far[u]) DFS(v,v);/// 轻链顶点必然是自己
}
}
LCA 计算结果部分
int LCA(int u,int v) /// 查询的两个点
{
int ans = 0 ;
while(top[u]!=top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
ans += query(id[top[u]],id[u],1); /// 线段树区间和，处理这条重链的贡献度
u = far[top[u]]; /// u 变为原链头得父亲节点，走轻边，继续计算贡献
}
if(u==v) return ans ; /// 如果两点重合，则返回，反之则在一条链上，继续计算两点间的贡献
if(id[u] > id[v]) swap(u,v);
return ans + query(id[son[u]] , id[v] , 1 ) ;
}
线段树部分
void pushup(int id)
{
tree[id].sum = tree[lc].sum + tree[rc].sum ;
}
void build(int l,int r,int id)
{
tree[id].l = l , tree[id].r = r ;
if(l==r){
tree[id].sum = val[rk[l]] ;
return ;
}
int mid = (l+r)>>1;
build(l,mid,lc) , build(mid+1,r,rc) , pushup(id) ;
}
void up(int pos,int x,int id)
{
if(tree[id].l==pos && tree[id].r==pos){
tree[id].sum = x ;
return ;
}
int mid = (tree[id].l+tree[id].r)>>1;
if(pos<=mid) up(pos,x,lc);
else up(pos,x,rc);
pushup(id);
}
int query(int l,int r,int id)
{
if(tree[id].l>r || tree[id].r<l) return 0 ;
if(l<=tree[id].l && tree[id].r<=r) return tree[id].sum ;
int mid = (tree[id].l+tree[id].r)>>1 , ans = 0;
if(l<=mid) ans+=query(l,r,lc);
if(r>mid) ans+=query(l,r,rc);
return ans;
}
题解
分四步进行：
第一：DFS处理每个节点的son，sz，dep，far，val值，即【DFS_init()部分】
第二：DFS进行树链刨分，处理出top，id，rk值【DFS()部分】
第三：写线段树【pushup，build，up，query，calc部分】
第四：执行操作
Housewife Wind’s Code 【边权区间查询】
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
#define lc id<<1
#define rc id<<1|1
#define test(x) cout<<"TEST "<<x<<endl;
const int mxn = 2e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 998244353 ;
using namespace std;
#define open freopen("input.in","r",stdin);freopen("output.in","w",stdout);
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
int p,t,n,m,k,si,res,cnt,lg,ans;
int top[mxn] , dep[mxn] , far[mxn] , sz[mxn] , val[mxn] , head[mxn] , id[mxn] , rk[mxn] , son[mxn] ;
struct ${int u,v,w;}no[mxn<<2];
struct $${int to,nx,w;}e[mxn<<2];
struct $$${int l,r,sum; }tree[mxn<<2];
void add(int u,int v,int w)
{
e[cnt].to = v , e[cnt].nx = head[u] , e[cnt].w = w , head[u] = cnt++;
}
void DFS_init(int u,int pre,int d,int w)
{
dep[u] = d , far[u] = pre , sz[u] = 1 , val[u] = w ;
for(int i=head[u];~i;i=e[i].nx){
int v = e[i].to ;
if(v==pre) continue ;
DFS_init(v,u,d+1,e[i].w);
sz[u]+=sz[v]; ///
if(sz[v]>sz[son[u]]) son[u] = v ; /// 更新重儿子
}
}
void DFS(int u,int x) ///
{
top[u] = x , id[u] = ++res , rk[res] = u ;
if(son[u]) DFS(son[u],x);
for(int i=head[u];~i;i=e[i].nx){
int v = e[i].to ;
if(v!=son[u] && v!=far[u]) DFS(v,v);/// 轻链
}
}
void pushup(int id)
{
tree[id].sum = tree[lc].sum + tree[rc].sum ;
}
void build(int l,int r,int id)
{
tree[id].l = l , tree[id].r = r ;
if(l==r){
tree[id].sum = val[rk[l]] ;
return ;
}
int mid = (l+r)>>1;
build(l,mid,lc) , build(mid+1,r,rc) , pushup(id) ;
}
void up(int pos,int x,int id)
{
if(tree[id].l==pos && tree[id].r==pos){
tree[id].sum = x ;
return ;
}
int mid = (tree[id].l+tree[id].r)>>1;
if(pos<=mid) up(pos,x,lc);
else up(pos,x,rc);
pushup(id);
}
int query(int l,int r,int id)
{
if(tree[id].l>r || tree[id].r<l) return 0 ;
if(l<=tree[id].l && tree[id].r<=r) return tree[id].sum ;
int mid = (tree[id].l+tree[id].r)>>1 , ans = 0;
if(l<=mid) ans+=query(l,r,lc);
if(r>mid) ans+=query(l,r,rc);
return ans;
}
int LCA(int u,int v)
{
int ans = 0 ;
while(top[u]!=top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
ans += query(id[top[u]],id[u],1);
u = far[top[u]];
}
if(u==v) return ans ;
if(id[u] > id[v]) swap(u,v);
return ans + query(id[son[u]] , id[v] , 1 ) ;
}
void init()
{
cnt = 0 , res = 0 ;
memset(head,-1,sizeof(head));
memset(sz,0,sizeof(sz));
memset(son,0,sizeof(son));
}
void solve()
{
while(~scanf("%d %d %d",&n,&m,&p)){
init();
for(int i=1;i<n;i++){
rd(no[i].u) , rd(no[i].v) , rd(no[i].w);
add(no[i].u,no[i].v,no[i].w);
add(no[i].v,no[i].u,no[i].w);
}
DFS_init(1,0,1,0);
DFS(1,1);
build(1,n,1);
for(int i=1,op,v,k,w;i<=m;i++){
rd(op);
if(op==1){
rd(k) , rd(w) ;
if(dep[no[k].u] > dep[no[k].v]) up(id[no[k].u],w,1);
else up(id[no[k].v],w,1);
} else {
rd(v);
printf("%d\n", LCA(p,v));
p = v ;
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
P1967 货车运输
树剖+线段树可以维护的是树上的点权区间，如果是边权区间的话就要边转点。
边化点，就是把边权转化为点权来用。而又因为每个点的父亲是唯一的，所以我们都是把边权给了深度更大的那个点。
