树链剖分——边权poj2763

时间:2021-09-30 05:46:15

边权操作起来也和点权一样,只要把边的权值映射到点上即可,要注意的地方是向上爬的过程中和点权不太一样,还有个特判(WA了几次。。)

完整代码

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 100005
struct E{int x,y;}e[maxn];
struct Edge{int to,nxt,w;}edge[maxn<<];
int head[maxn],tot,v[maxn],n,q,c;
void init(){memset(head,-,sizeof head);tot=;}
void addedge(int u,int v,int w){
edge[tot].to=v;edge[tot].w=w;edge[tot].nxt=head[u];head[u]=tot++;
}
int f[maxn],son[maxn],d[maxn],size[maxn];
void dfs1(int x,int pre,int deep){
size[x]=,d[x]=deep,f[x]=pre;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y==pre)continue;
v[y]=edge[i].w;//注意这里将边权映射到点上
dfs1(y,x,deep+);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
int cnt,top[maxn],id[maxn],rk[maxn];
void dfs2(int x,int tp){
top[x]=tp;id[x]=++cnt;rk[cnt]=x;
if(son[x])dfs2(son[x],tp);
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y!=f[x] && y!=son[x])dfs2(y,y);
}
} #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<];
void pushup(int rt){sum[rt]=sum[rt<<]+sum[rt<<|];}
void build(int l,int r,int rt){
if(l==r){sum[rt]=v[rk[l]];return;}
int m=l+r>>;
build(lson);build(rson);
pushup(rt);
}
void update(int pos,int l,int r,int rt,int v){
if(l==r){sum[rt]=v;return;}
int m=l+r>>;
if(pos<=m)update(pos,lson,v);
else update(pos,rson,v);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return sum[rt];
int m=l+r>>,res=;
if(L<=m)res+=query(L,R,lson);
if(R>m)res+=query(L,R,rson);
return res;
} int Query(int x,int y){
int res=;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
res+=query(id[top[x]],id[x],,n,);
x=f[top[x]];
}
if(x==y)return res;
if(id[x]>id[y])swap(x,y);
return res+query(id[son[x]],id[y],,n,);
} int main(){
init();int s;
scanf("%d%d%d",&n,&q,&s);
for(int i=;i<n;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
e[i].x=x;e[i].y=y;
addedge(x,y,z);addedge(y,x,z);
}
cnt=;dfs1(s,,);dfs2(s,s);
build(,n,);
while(q--){
int op,x,y;
scanf("%d",&op);
if(op==){scanf("%d",&x);
cout<<Query(s,x)<<'\n';s=x;}
if(op==){
scanf("%d%d",&x,&y);
int u=e[x].x,v=e[x].y;
if(d[u]<d[v])swap(u,v);
update(id[u],,n,,y);
}
}
}

不同之处:最后一次查询的时候不要最高的那个点权

特判:x==y的时候直接返回即可

int Query(int x,int y){
int res=;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
res+=query(id[top[x]],id[x],,n,);
x=f[top[x]];
}
if(x==y)return res;
if(id[x]>id[y])swap(x,y);
return res+query(id[son[x]],id[y],,n,);
}