首页 > 代码库 > SPOJ 375 Query on a tree
SPOJ 375 Query on a tree
Desciption
给出一个树,每条边有边权,支持两种操作,询问 \(u,v\) 路径上边权最大值,修改第 \(i\) 条边的边权,\(n\leqslant 10^4,T\leqslant 10\)
Sol
树链剖分.
基于边的树链剖分,对于一个点,可能有许多儿子,但是它只能有一个父亲,给它编号表示它到它父亲的边,只需要修改查询的是最后一步就可以了.
Code
#include<cstdio>#include<vector>#include<iostream>using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "#define mid ((l+r)>>1)#define lc (o<<1)#define rc (o<<1|1)const int N = 10005;inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }int n,e,cnt;struct Edge{ int fr,to,v; }edge[N];vector<Edge> g[N];int f[N],cost[N],dep[N],son[N],top[N],sz[N],p[N];int d[N<<2];void Add_Edge(int fr,int to,int v){ edge[++e]=(Edge){ fr,to,v }; g[fr].push_back((Edge){ fr,to,v }); g[to].push_back((Edge){ to,fr,v });}void DFS1(int u,int fa){ sz[u]=1,son[u]=0,dep[u]=dep[fa]+1,f[u]=fa; for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i].to)!=fa){ DFS1(v,u),sz[u]++; if(!son[u]||sz[son[u]]<sz[v]) son[u]=v; }}void DFS2(int u,int tp){ p[u]=++cnt,top[u]=tp; if(son[u]) DFS2(son[u],tp); for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i].to)!=f[u]&&v!=son[u]) DFS2(v,v);}void Build(int o,int l,int r){ if(l==r){ d[o]=cost[l];return; } Build(lc,l,mid),Build(rc,mid+1,r); d[o]=max(d[lc],d[rc]);}void Change(int o,int l,int r,int x,int v){ if(l==r){ d[o]=v;return; } if(x<=mid) Change(lc,l,mid,x,v); else Change(rc,mid+1,r,x,v); d[o]=max(d[lc],d[rc]);}int QueryMax(int o,int l,int r,int L,int R){ if(L<=l&&r<=R) return d[o];int res=0; if(L<=mid) res=max(res,QueryMax(lc,l,mid,L,R)); if(R>mid) res=max(res,QueryMax(rc,mid+1,r,L,R)); return res;}int GetAns(int u,int v){ int res=0,f1=top[u],f2=top[v]; while(f1!=f2){ if(dep[f1]<dep[f2]) swap(u,v),swap(f1,f2); res=max(res,QueryMax(1,1,n,p[f1],p[u])); u=f[f1],f1=top[u]; } if(dep[u]>dep[v]) swap(u,v); if(dep[v]==dep[u]) return res; else return max(res,QueryMax(1,1,n,p[u]+1,p[v]));}void clr(){ for(int i=0;i<N;i++) g[i].clear();cnt=0,e=0; }int main(){// freopen("in.in","r",stdin);// freopen("out.out","w",stdout); ios::sync_with_stdio(false); for(int T=in();T--;){ clr(); n=in(); for(int i=1,a,b,c;i<n;i++) a=in(),b=in(),c=in(),Add_Edge(a,b,c); DFS1(1,1),DFS2(1,1); for(int i=1;i<n;i++){ int a=edge[i].fr,b=edge[i].to; if(dep[a]>dep[b]) swap(a,b),swap(edge[i].fr,edge[i].to); cost[p[b]]=edge[i].v; } Build(1,1,n); for(char opt[10];;){ scanf("%s",opt); if(opt[0]==‘D‘) break; int a=in(),b=in(); if(opt[0]==‘C‘) Change(1,1,n,p[edge[a].to],b); else printf("%d\n",GetAns(a,b));// debug(QueryMax(1,1,n,1,1)),debug(QueryMax(1,1,n,2,2)),debug(QueryMax(1,1,n,3,3))<<endl; } }return 0;}
SPOJ 375 Query on a tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。