[SPOJ375 QTREE]树链剖分、例题

【题目大意】
给定一棵树,然后给出两种操作:
1、改变某条边的权值
2、询问点x到点y的路径上,长度最长的边的长度是多少?
【算法分析】
我是按照漆子超大神的论文做的。
他如是说道:
对于一棵树,定义Size(u)为以u为根的子树的结点数。
然后对于u与所有儿子v相连的边而言,Size(v)最大的,那条边就叫重边,其它边都是轻边。
Then,有一个重要结论:
每个点到根的路径上都不超过O(lg N)条轻边和O(lg N)条重路径。
(重路径是由重边连续连成的)
然后我们对于每个询问(x,y)的路径,就可以分成(x,lca(x,y))的路径和(y,lca(x,y))的路径。
于是问题变成怎么求x到它一个祖先结点的边权的最大值。
我们就可以轻边直接算,重路径利用线段树求解。
最终就可以在O(Q lg ^2 n)的复杂度得到解。(Q问询问个数)
至于具体实现的话,我是把连续的重边先DFS,然后再DFS其它轻边。
弄一个队列装起来,这样DFS完以后就可以保证连续的重边(重路径)在队列里是连续的。
然后就把连续的重路径涂上同一个颜色。在记录一下这种颜色在队里里起始点是哪。
方便后面利用。
至于求lca我是利用的经典的转化为RMQ求解。
当然,少不了N个指向数组指来指去。。。。,指到头都晕了。

【用到的东西】
LCA——>RMQ
线段树
【其它】
我那叫一个激动啊。。200+行,5KB的程序一次过样例,一次AC!
3552963 2010-04-24 18:16:42 cwj Query on a tree accepted 4.25 6.0M

C++

4.0.0-8

时间有点丑,大概是因为我每次都memset的关系吧。。。
不过能A就成。。。
【CODE】
#include #include #include #define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int E=20005;
const int N=10005;
const int INF=1000000000;
struct edge{int x,y,w,next,op,heavy,inlist;}g[E];
struct Node{int l,r,data;}tr[E*5];
int n,Tc,e,heavytot,ctot,rmqtot,ans,nowdep;
int ls[N],Size[N],dep[N],fa[N];
int heavyedge[N],color[E],colorst[E];
int R[E],rmq[16][E],lg[E];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}

void addedge(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w;
g[e].next=ls[x]; ls[x]=e;
}

void init(){
e=0;
heavytot=0;
ctot=0;
rmqtot=0;
memset(ls,0,sizeof(ls));
memset(heavyedge,0,sizeof(heavyedge));
memset(Size,0,sizeof(Size));
memset(g,0,sizeof(g));
memset(fa,0,sizeof(fa));
memset(color,0,sizeof(color));
memset(colorst,0,sizeof(colorst));
memset(R,0,sizeof(R));
memset(rmq,0,sizeof(rmq));

char op[100];
int x,y,w,i;

scanf("%d",&n);
for (i=1;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
g[e].op=i+n-1;
}
for (i=1;i addedge(g[i].y,g[i].x,g[i].w);
g[e].op=i;
}
}

void Get_Size(int p,int &times){
rmq[0][++rmqtot]=dep[p];
R[p]=rmqtot;
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
Get_Size(g[t].y,times);
rmq[0][++rmqtot]=dep[p];
}
Size[p]=times-Size[p];
}

void Get_heavyedge(int p){
int zz=0,mm=0;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && Size[g[t].y]>mm){
mm=Size[g[t].y];
zz=t;
}
if (!zz) return;
heavyedge[++heavytot]=zz;
g[zz].heavy=1;
g[zz].inlist=heavytot;
g[g[zz].op].heavy=1;
g[g[zz].op].inlist=heavytot;
Get_heavyedge(g[zz].y);

for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && t!=zz)
Get_heavyedge(g[t].y);
}

void draw_color(){
ctot=1; color[heavyedge[1]]=1; colorst[1]=1;
for (int i=2;i<=heavytot;i++){
int &t=heavyedge[i],&pt=heavyedge[i-1];
if (g[pt].y!=g[t].x){
ctot++;
colorst[ctot]=i;
}
color[t]=ctot;
color[g[t].op]=ctot;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r;
if (l==r){
tr[p].data=g[heavyedge[l]].w;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

void buildrmq(){
int i,k;
lg[1]=0;
for (i=2;i<=rmqtot;i++){
lg[i]=lg[i-1];
if (1< }
for (k=1;(1< for (i=1;i+(1< rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<}

void pre_work(){
int tmp=0;
dep[1]=1;
fa[1]=0;
Get_Size(1,tmp);
Get_heavyedge(1);
draw_color();
build(1,1,heavytot);
buildrmq();
}

void Change(int p,int pos){
if (tr[p].l==tr[p].r){
tr[p].data=g[heavyedge[pos]].w;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (pos<=mid) Change(p*2,pos);
else Change(p*2+1,pos);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

int getmin(int x,int y){
if (x>y) swap(x,y);
int step=lg[y-x+1];
return min(rmq[step][x],rmq[step][y-(1<}

int getmax(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r) return tr[p].data;
int tmp1=-INF,tmp2=-INF,mid=(tr[p].l+tr[p].r)/2;
if (l<=mid) tmp1=getmax(p*2,l,r);
if (r>=mid+1) tmp2=getmax(p*2+1,l,r);
return max(tmp1,tmp2);
}

void Try(int x){
if (dep[x]==nowdep) return;
if (g[fa[x]].heavy){
int &p=g[heavyedge[colorst[color[fa[x]]]]].x,tmp;
if (dep[p]>=nowdep){
Try(p);
tmp=getmax(1,colorst[color[fa[x]]],g[fa[x]].inlist);
ans=max(ans,tmp);
}
else{
tmp=getmax(1,g[fa[x]].inlist-(dep[x]-nowdep-1),g[fa[x]].inlist);
ans=max(ans,tmp);
}
}
else{
Try(g[fa[x]].x);
ans=max(ans,g[fa[x]].w);
}
}

void solve(){
char op[100];
int x,y;
for (;;){
scanf("%s",op+1);
if (op[1]==’D’) return;
if (op[1]==’C’){
scanf("%d%d",&x,&y);
g[x].w=y;
g[g[x].op].w=y;
if (g[x].heavy) Change(1,g[x].inlist);
}
else{
ans=0;
scanf("%d%d",&x,&y);
nowdep=getmin(R[x],R[y]);
Try(x);
Try(y);
printf("%dn",ans);
}
}
}

int main(){
scanf("%d",&Tc);
for (int i=0;i init();
pre_work();
solve();
}
}

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注