SPOJ - QTREE (树链剖分)

本文主要是介绍SPOJ - QTREE (树链剖分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    基础的树链剖分题目，不过是边权，可以向下映射成点权或者按边剖分。

VIEW CODE

#include <iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<string>
using namespace std;
const int mmax=10010;
const int inf=0x3fffffff;
struct edge
{int st,en,cost;int next;
}E[2*mmax];
int p[mmax],fa[mmax],son[mmax],top[mmax],ID[mmax];
int deep[mmax],cost[mmax],id_[mmax];
bool vis[mmax];
int num;
void add(int st,int en,int cost)
{E[num].st=st;E[num].en=en;E[num].cost=cost;E[num].next=p[st];p[st]=num++;
}
void init()
{memset(p,-1,sizeof p);num=0;
}
struct tree
{int l,r;int max_n;int mid(){return (l+r)>>1;}
}T[4*mmax];
void build(int id,int l,int r)
{T[id].l=l,T[id].r=r;if(l==r){T[id].max_n=cost[ID[l]];return ;}int mid=T[id].mid();build(id<<1,l,mid);build(id<<1|1,mid+1,r);T[id].max_n=max(T[id<<1].max_n,T[id<<1|1].max_n);
}
void updata(int id,int pos,int val)
{if(T[id].l==T[id].r){T[id].max_n=val;return ;}int mid=T[id].mid();if(mid>=pos)updata(id<<1,pos,val);elseupdata(id<<1|1,pos,val);T[id].max_n=max(T[id<<1].max_n,T[id<<1|1].max_n);
}
int query(int id,int l,int r)
{if(l<=T[id].l&&T[id].r<=r)return T[id].max_n;int mid=T[id].mid();int ans=0;if(mid>=l)ans=max(ans,query(id<<1,l,r));if(mid<r)ans=max(ans,query(id<<1|1,l,r));return ans;
}
int dfs(int u)
{vis[u]=1;int cnt=1,tmp=0,e=0,Co=inf;for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;int len=E[i].cost;if(!vis[v]){fa[v]=u;deep[v]=deep[u]+1;cost[v]=len;int tt=dfs(v);cnt+=tt;if(tmp<tt){tmp=tt;e=v;Co=len;}}}son[u]=e;return cnt;
}
int now_cnt;
void new_id(int u)
{ID[now_cnt]=u;id_[u]=now_cnt;now_cnt++;vis[u]=1;if(son[u]){top[son[u]]=top[u];new_id(son[u]);}for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;if(!vis[v])new_id(v);}
}
int solve(int x,int y)
{int ans=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);ans=max(ans,query(1,id_[top[x]],id_[x]));x=fa[top[x]];}if(x!=y){if(deep[x]>deep[y])swap(x,y);ans=max(ans,query(1,id_[son[x]],id_[y]));}return ans;
}
char str[20];
int main()
{int t,n;scanf("%d",&t);while(t--){init();scanf("%d",&n);for(int i=0;i<n-1;i++){int u,v,cost;scanf("%d %d %d",&u,&v,&cost);add(u,v,cost);add(v,u,cost);}fa[1]=1;deep[1]=0;cost[1]=0;memset(vis,0,sizeof vis);for(int i=1;i<=n;i++)top[i]=i;dfs(1);memset(vis,0,sizeof vis);now_cnt=1;new_id(1);
//        for(int i=1;i<=n;i++)
//            cout<<son[i]<<" ";
//        cout<<endl;
//        system("pause");build(1,1,n);while(1){int a,b;scanf("%s",str);if(!strcmp(str,"DONE"))break;scanf("%d %d",&a,&b);if(!strcmp(str,"QUERY"))printf("%d\n",solve(a,b));if(!strcmp(str,"CHANGE")){int st=E[2*a-2].st;int en=E[2*a-2].en;if(deep[st]>deep[en])swap(st,en);updata(1,id_[en],b);}}//system("pause");}return 0;
}

这篇关于SPOJ - QTREE (树链剖分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---