竹子听

我的树链剖分,检查了一遍还没有投入使用,不知正确性

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 10000

#define max(x,y) x>y?x:y

int n,M,fa[maxn],top[maxn],siz[maxn],hchild[maxn],deep[maxn],id[maxn],iid[maxn],tree[maxn<<2];

int pre[maxn],to[maxn],next[maxn],weight[maxn],wei[maxn],num=0,tip=0;

void clear()

{

memset(fa,0,sizeof(int));

memset(top,0,sizeof(int));

memset(siz,0,sizeof(int));

memset(hchild,0,sizeof(int));

memset(id,0,sizeof(int));

memset(iid,0,sizeof(int));

memset(weight,0,sizeof(int));

memset(wei,0,sizeof(int)); 

}

void addedge(int x,int y,int z)

{num++; next[num]=pre[x],pre[x]=num,to[num]=y,weight[num]=z;}

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

void build(int x)

{

for(M=1;M<x;M<<=1);

for(int i=0;i<tip;i++) idd[id[i]]=i;//id:节点父边->编号  iid:编号->节点父边 

for(int i=M;i<M+n;i++) tree[i]=wei[iid[i-M]];

}

void updata()

{

for(i=M-1;i>=1;i--) tree[i]=max(tree[i>>1],tree[i>>1|1]);

}

void query(int x,int y)

{

int ans=0;

x+=M,y+=M;

x++,y--;

while(1)

{

if(x%2==0)ans=max(ans,tree[x|1]);

if(y%2==1)ans=max(ans,tree[y|0]);

x<<=1,y<<=1; 

if(x+1==y) break;

}

return ans;

}

void dfs1(int father,int now,int depth)

{

int p=pre[now];

deep[now]=depth;

if(!p){siz[now]=1;return;}

while(p)

{

if(to[p]==father) {p=next[p];continue;}

father[to[p]]=now;

dfs1(now,to[p],depth+1);

siz[now]+=siz[to[p]];

if(siz[to[p]]>siz[hchild[now]]) hchild[now]=to[p];

p=next[p];

}

}

void dfs2(int father,int now,int tp,int weig)

{

int p=pre[now];

top[now]=tp;

id[now]=tip++;//id是所在点所在父边的编号,满足同一条重链上的点编号连续 

wei[now]=weig;//wei表示now的父边的权值 

if(!p) return;

if(hchild[now]) 

while(p)

{

if(to[p]==hchild[now]) {dfs2(now,hchild[now],tp,weight[p]);break;}

else p=next[p];

}

p=pre[now];

while(p)

{

if(to[p]==father||to[p]==hchild[now]) {p=next[p];continue;}

dfs2(now,to[p],to[p],weight[p]);

p=next[p];

}

}

int ask_max(int u,int v)

{

int t1=top[u],t2=top[v],ans=0;

while(t1!=t2)

{

if(deep[u]<deep[v]){swap(u,v),swap(t1,t2);}

ans=max(ans,query(id[u],id[t1]));

u=fa[top[u]],t1=top[u];

}

if(u==v) return ans;

if(deep[u]<deep[v]){swap(u,v),swap(t1,t2);}

ans=max(ans,query(id[hchild[u]],id[v]));

return ans;

}

int main()

{

int temp1,temp2,temp3;

clear();

scanf("%d",&n);

for(int i=1;i<=n+1;i++)

{

scanf("%d%d%d",&temp1,&temp2,&temp3);//在这里权值应该在这里一起处理 

addedge(temp1,temp2,temp3);

addedge(temp2,temp1,temp3);

}

dfs1(1,1,1);

dfs2(1,1,1,0);

build(tip-1);

updata();

query(temp1,temp2);

}


评论