题目传送门:[SPOJ - QTREE] Query on a tree https://vjudge.net/problem/13013/origin
http://poj.org/problem?id=1679
题目大意:
存在一个树, 树上有 n 个节点和 n-1 条边, 对这棵树进行以下两种操作
CHANGE i ti : 将树的第 i 条边的权值改为 ti
QUERY a b : 查询 a->b 路径中权值最大的边的值
分析:
边权树链剖分裸题, CHANGE 操作是更改第 i 条边, 因此边用结构体数组将其保存, 用边
的两个点中深度较大的点记录边的权值, 更改时更改该点, 为了方便操作, 两次 dfs 之后
重新遍历保存边的结构体数组, 将深度较大的边存在 E[i].u 中. 更新时更新该点即可.
注意: 因为用深度较大的点记录该边的权值, x 点所记录的权值是边 x->fa[x] 的权值, 因此在
对 x->y 路径进行操作时, 其实是对 son[x]->y 的点所记录的权值进行操作.
线段树维护区间最大值, 查询为区间查询
代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- const int MAX=10000;
- const int INF=1<<29;
- int head[MAX],cnt;
- int fa[MAX],deep[MAX],son[MAX],size[MAX],top[MAX],id[MAX],rk[MAX],tot;
- int t,n,x,y,a[MAX];
- int tree[MAX<<2];
- char op[10];
- struct Edge{
- int next,to;
- }edge[MAX*2];
- void add(int u,int v)
- {
- edge[cnt].to=v;
- edge[cnt].next=head[u];
- head[u]=cnt++;
- }
- struct E{ // 记录边信息
- int u,v,w;
- }e[MAX];
- void dfs1(int u,int f,int d)
- {
- fa[u]=f;
- deep[u]=d;
- size[u]=1;
- for(int i=head[u];i!=-1;i=edge[i].next)
- {
- int v=edge[i].to;
- if(v!=fa[u])
- {
- dfs1(v,u,d+1);
- size[u]+=size[v];
- if(son[u]==-1||size[v]>size[son[u]])
- son[u]=v;
- }
- }
- }
- void dfstop(int u,int t)
- {
- top[u]=t;
- id[u]=tot++;
- rk[id[u]]=u;
- if(son[u]==-1)return;
- dfstop(son[u],t);
- for(int i=head[u];i!=-1;i=edge[i].next)
- {
- int v=edge[i].to;
- if(v!=son[u]&&v!=fa[u])
- dfstop(v,v);
- }
- }
- void PushUp(int rt) // 维护区间最大值
- {
- tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
- }
- void Build(int l,int r,int rt)
- {
- if(l==r)
- {
- tree[rt]=a[rk[l]];
- return;
- }
- int m=l+r>>1;
- Build(ls),Build(rs);
- PushUp(rt);
- }
- void Update(int pos,int val,int l,int r,int rt)// 单点更新
- {
- if(l==r)
- {
- tree[rt]=val;
- return;
- }
- int m=l+r>>1;
- if(pos<=m)Update(pos,val,ls);
- else Update(pos,val,rs);
- PushUp(rt);
- }
- int Query(int L,int R,int l,int r,int rt)// 区间查询
- {
- if(L<=l&&r<=R)
- return tree[rt];
- int ans=-INF;
- int m=l+r>>1;
- if(L<=m)ans=max(ans,Query(L,R,ls));
- if(R>m)ans=max(ans,Query(L,R,rs));
- return ans;
- }
- int solve(int x,int y)// 查询 x->y 路径中边权最大的值
- {
- int ans=-INF;
- while(top[x]!=top[y])
- {
- if(deep[top[x]]<deep[top[y]])
- swap(x,y);
- ans=max(ans,Query(id[top[x]],id[x],1,tot,1));
- x=fa[top[x]];
- }
- if(deep[x]>deep[y])
- swap(x,y);
- ans=max(ans,Query(id[son[x]],id[y],1,tot,1));//x->y 路径的权值记录在 son[x]->y 之间, x 点记录的是 x 到其父亲节点的权值
- return ans;
- }
- void init()
- {
- memset(head,-1,sizeof(head));cnt=0;
- memset(son,-1,sizeof(son));tot=1;
- memset(tree,0,sizeof(tree));
- memset(a,0,sizeof(a));
- }
- int main()
- {
- scanf("%d",&t);
- while(t--)
- {
- init();
- scanf("%d",&n);
- for(int i=1;i<n;i++)
- {
- scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
- add(e[i].u,e[i].v),add(e[i].v,e[i].u);
- }
- dfs1(1,-1,0),dfstop(1,1);
- for(int i=1;i<n;i++)
- {
- if(deep[e[i].u]<deep[e[i].v]) // 将边两边的点深度较大的点记录在 u 中
- swap(e[i].u,e[i].v);
- a[e[i].u]=e[i].w; // 深度较大的点保存该边的权值
- }
- Build(1,tot,1);
- while(scanf("%s",op))
- {
- if(op[0]=='D')break;
- if(op[0]=='C')
- {
- scanf("%d%d",&x,&y);
- Update(id[e[x].u],y,1,tot,1); // 更新深度较大的点的权值即更新该边的权值
- }
- if(op[0]=='Q')
- {
- scanf("%d%d",&x,&y);
- printf("%d\n",solve(x,y));
- }
- }
- }
- return 0;
- }
- [SPOJ - QTREE] Query on a tree
来源: http://www.bubuko.com/infodetail-3050173.html