题目大意
一棵树上有$n$个节点，编号分别为$1$到$n$，每个节点都有一个权值$w$
对这棵树完成一些操作，分三种
把结点$u$的权值改为$t$
询问从点$u$到点$v$的路径上的节点的最大权值
询问从点$u$到点$v$的路径上的节点的权值和
注意：从点$u$到点$v$的路径上的节点包括$u$和$v$本身
数据范围
$1\leqslant n\leqslant 30000,0\leqslant q\leqslant 200000$
中途操作中保证每个节点的权值$-30000\leqslant w \leqslant 30000$
树链剖分题解
因为这是点权的统计所以可以想到可以用很基础的树链剖分来做
树链剖分其实就是把树拆成一个链用数据结构维护一般用线段树
通常的剖分方法是把每条树边标记轻重边每个节点对其子节点只连一条重边其他全是轻边
而当重边连接的是拥有最大子树的子节点时均摊的时间复杂度是最优的全是重边的路径我们称其为重路径
因此我们在第一次深搜的时候把每个子树大小记录在其根节点上还要记录每个节点的父亲节点和深度这样方便执行树链剖分和之后的操作
标记好之后重路径上的点其实就是整棵树的所有节点第二次深搜的时候就把每条重路径连起来给每个节点一个位置编号
有了位置编号之后每次操作就可以用数据结构维护
修改操作
1. 单独修改一个点的权值
根据其编号直接在数据结构中修改就行了
2.修改点$u$和点$v$的路径上的权值
1若$u$和$v$在同一条重链上
直接用数据结构修改$u$至$v$间的值
2若$u$和$v$不在同一条重链上
一边进行修改一边将$u$和$v$往同一条重链上靠然后就变成了情况1
查询操作
查询操作的分析过程同修改操作
动态树题解
埋坑中
程序
动态树
Time:5436ms Memory:3104kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,q,top,cnt;
int fa[30005],last[30005],c[30005][2],val[30005],mx[30005],sum[30005],st[30005];
bool rev[30005];
struct edge{int to,next;}e[60005];
void insert(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;}
bool isroot(int x){return (c[fa[x]][0]!=x)&&(c[fa[x]][1]!=x);}
void update(int x){
int l=c[x][0],r=c[x][1];
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],val[x]);
sum[x]=sum[l]+sum[r]+val[x];
}
void pushdown(int x){
int l=c[x][0],r=c[x][1];
if (rev[x]){
rev[x]^=1;
rev[l]^=1,rev[r]^=1;
swap(c[x][0],c[x][1]);
}
}
void rotate(int &x){
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;r=l^1;
if(!isroot(y)){
if(c[z][0]==y)c[z][0]=x;
else c[z][1]=x;
}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(y);update(x);
}
void splay(int x){
top=0;st[++top]=x;
for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
while(top) pushdown(st[top--]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)){
if(c[y][0]==x^c[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x){
for(int t=0;x;t=x,x=fa[x])
splay(x),c[x][1]=t,update(x);
}
void dfs(int x){
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x]){
fa[e[i].to]=x;
dfs(e[i].to);
}
}
inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}
inline void querymx(int x,int y){makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);}
inline void querysum(int x,int y){makeroot(x);access(y);splay(y);printf("%d\n",sum[y]);}
inline void change(int x,int v){access(x);splay(x);val[x]=v;update(x);}
int main(){
mx[0]=-inf;
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
}
dfs(1);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
val[i]=mx[i]=sum[i]=x;
}
scanf("%d",&q);
char ch[5];int x,y;
while(q--){
scanf("%s",ch+1);
scanf("%d%d",&x,&y);
if(ch[2]=='M')querymx(x,y);
else if(ch[2]=='S')querysum(x,y);
else change(x,y);
}
return 0;
}树链剖分
Time:2624ms Memory:12924kb
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
struct edge{int next,to;}e[60050];
struct tree{int mx,sum;}t[1200050];
int last[30050],deep[30050],fa[30050],flag[30050],size[30050],v[30050];
int top[30050],d[30050];
int n,m,dfs_tot,edge_tot;
inline void addedge(int u,int v){e[++edge_tot].to=v;e[edge_tot].next=last[u];last[u]=edge_tot;}
inline int lca(int a,int b){
while(1){
if (top[a]==top[b]) return deep[a]<=deep[b]?a:b;
else if (deep[top[a]]>=deep[top[b]]) a=fa[top[a]];
else b=fa[top[b]];
}
}
inline void init(){
scanf("%d",&n);
For(i,1,n-1){
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
For(i,1,n) scanf("%d",&v[i]);
}
void dfs(int p){
flag[p]=size[p]=1;
goedge(i,p)
if (!flag[e[i].to]){
fa[e[i].to]=p;
deep[e[i].to]=deep[p]+1;
dfs(e[i].to);
size[p]+=size[e[i].to];
}
}
void gochain(int p,int chain_tot){
d[p]=++dfs_tot;top[p]=chain_tot;
int k=0;
goedge(i,p)
if ((deep[e[i].to]>deep[p])&&(size[e[i].to]>size[k])) k=e[i].to;
if (!k) return;
gochain(k,chain_tot);
goedge(i,p)
if ((deep[e[i].to]>deep[p])&&(e[i].to!=k)) gochain(e[i].to,e[i].to);
}
void build(int p,int nowl,int nowr){
t[p].mx=-30050;
if (nowl==nowr) return;
int mid=(nowl+nowr)>>1;
build(p<<1,nowl,mid);
build(p<<1|1,mid+1,nowr);
}
void change(int p,int nowl,int nowr,int x,int c){
if (nowl==nowr){t[p].mx=c;t[p].sum=c;return;}
int mid=(nowl+nowr)>>1;
if (x<=mid) change(p<<1,nowl,mid,x,c);
if (x>mid) change(p<<1|1,mid+1,nowr,x,c);
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
int findmax(int p,int nowl,int nowr,int l,int r){
if ((nowl==l)&&(nowr==r)) return t[p].mx;
int mid=(nowl+nowr)>>1;
if (r<=mid) return findmax(p<<1,nowl,mid,l,r);
else if (l>mid) return findmax(p<<1|1,mid+1,nowr,l,r);
else{
int s1=findmax(p<<1,nowl,mid,l,mid);
int s2=findmax(p<<1|1,mid+1,nowr,mid+1,r);
return max(s1,s2);
}
}
int findsum(int p,int nowl,int nowr,int l,int r){
if ((nowl==l)&&(nowr==r)) return t[p].sum;
int mid=(nowl+nowr)>>1;
if (r<=mid) return findsum(p<<1,nowl,mid,l,r);
else if (l>mid) return findsum(p<<1|1,mid+1,nowr,l,r);
else return findsum(p<<1,nowl,mid,l,mid)+findsum(p<<1|1,mid+1,nowr,mid+1,r);
}
inline int qmax(int low,int high){
int result=-30001;
while (top[low]!=top[high]){
result=max(result,findmax(1,1,n,d[top[low]],d[low]));
low=fa[top[low]];
}
result=max(result,findmax(1,1,n,d[high],d[low]));
return result;
}
inline int qsum(int low,int high){
int result=0;
while (top[low]!=top[high]){
result+=findsum(1,1,n,d[top[low]],d[low]);
low=fa[top[low]];
}
result+=findsum(1,1,n,d[high],d[low]);
return result;
}
int main(){
init();
dfs(1);
gochain(1,1);
build(1,1,n);
For(i,1,n) change(1,1,n,d[i],v[i]);
scanf("%d",&m);
For(i,1,m){
char ch[10];
scanf("%s",ch);
if (ch[1]=='M'){
int a,b;
scanf("%d%d",&a,&b);
int h=lca(a,b);
printf("%d\n",max(qmax(a,h),qmax(b,h)));
}
else if (ch[1]=='S'){
int a,b;
scanf("%d%d",&a,&b);
int h=lca(a,b);
printf("%d\n",qsum(a,h)+qsum(b,h)-v[h]);
}
else{
int a,b;
scanf("%d%d",&a,&b);
change(1,1,n,d[a],b);
v[a]=b;
}
}
return 0;
}
鄂公网安备 42010202000505 号