我的树链剖分,检查了一遍还没有投入使用,不知正确性
#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);
}
评论