首页 > 代码库 > QtreeⅠ
QtreeⅠ
题意:https://vjudge.net/problem/SPOJ-QTREE
带修路径查询最大边权
sol :树链剖分,之后每条重链就是一个连续的区间,拿线段树维护即可
简单讲讲链剖吧.....就是把树边划分为轻重边,重边的定义是和siz最大的儿子之间的边
通过两次dfs实现,可以证明重链(重边形成的链)不超过logn条
直接上代码吧,复杂度O(nlogn^2)
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Mx=10010; struct Edge { int x,y,val; } edge[Mx]; struct Tree { int l,r,val; } tree[4*Mx]; int n,cnt,dep[Mx],siz[Mx],fa[Mx],num[Mx],son[Mx],top[Mx];//top表示最近的重链父节点 int tot,nxt[2*Mx],head[Mx],ver[2*Mx],val[2*Mx]; void clear() { memset(head,0,sizeof(head)); memset(son,0,sizeof(son)); cnt=0;tot=0; } inline void add(int x,int y,int z) { tot++; nxt[tot]=head[x]; ver[tot]=y; val[tot]=z; head[x]=tot; } //链剖 void dfs1(int u,int Fa,int Dep) { dep[u]=Dep,siz[u]=1,son[u]=0,fa[u]=Fa; for(int i=head[u];i;i=nxt[i]) { int v=ver[i]; if(v==Fa) continue; dfs1(v,u,Dep+1); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } } void dfs2(int u,int Top) { top[u]=Top,num[u]=++cnt; if(son[u]) dfs2(son[u],Top); for(int i=head[u];i;i=nxt[i]) { int v=ver[i]; if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } //线段树 void pushup(int x) { tree[x].val=max(tree[x<<1].val,tree[x<<1|1].val); } void build(int l,int r,int v) { tree[v].l=l;tree[v].r=r; if(l==r) { tree[v].val=val[l]; return ; } int mid=(l+r)>>1; build(l,mid,v*2); build(mid+1,r,v*2+1); pushup(v); } void update(int u,int v,int val) { if(tree[u].l==tree[u].r) { tree[u].val=val; return ; } int mid=(tree[u].l+tree[u].r)/2; if(v<=mid) update(u*2,v,val); else update(u*2+1,v,val); pushup(u); } int query(int x,int l, int r) { if(tree[x].l>=l&&tree[x].r<=r) return tree[x].val; int ans=0,mid=(tree[x].l+tree[x].r)/2; if(l<=mid) ans=max(ans,query(x<<1,l,r)); if(r>mid) ans=max(ans,query(x<<1|1,l,r)); return ans; } int solve(int u,int v) { int ans=0,Top1=top[u],Top2=top[v]; while(Top1!=Top2) { if(dep[Top1]<dep[Top2]) swap(Top1,Top2),swap(u,v); ans=max(ans,query(1,num[Top1],num[u])); u=fa[Top1];Top1=top[u]; } if(u==v) return ans; if(dep[u]>dep[v]) swap(u,v); ans=max(ans,query(1,num[son[u]],num[v])); return ans; } int main() { int T;scanf("%d",&T); while(T--) { clear(); scanf("%d",&n); for(int i=1,x,y,z;i<n;i++) { scanf("%d%d%d",&x,&y,&z); edge[i].x=x;edge[i].y=y;edge[i].val=z; add(x,y,z);add(y,x,z); } dfs1(1,0,1);dfs2(1,1); for(int i=1;i<n;i++) { if(dep[edge[i].x]<dep[edge[i].y]) swap(edge[i].x,edge[i].y); val[num[edge[i].x]]=edge[i].val; } build(1,cnt,1); while(1) { char s[200];scanf("%s",s);if(s[0]==‘D‘) break; int x,y; scanf("%d%d",&x,&y); if(s[0]==‘Q‘) printf("%d\n",solve(x,y)); if (s[0]==‘C‘) update(1,num[edge[x].x],y); } } return 0; }
QtreeⅠ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。