4月7日 我的树链剖分
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000
int n,fa[maxn],top[maxn],siz[maxn],hchild[maxn],deep[maxn],id[maxn];
int pre[maxn],to[maxn],next[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));
}
void addedge(int x,int y)
{num++; next[num]=pre[x],pre[x]=num,to[num]=y;}
void dfs1(int father,int now,int depth)
{
int p=pre[now];
fa[to[p]]=now;
deep[now]=depth;
if(!p)
{siz[now]=1;return;}
while(p)
{
if(to[p]==father)
{p=next[p];continue;}
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 p=pre[now];
top[now]=tp;
id[now]=tip++;
if(!p) return;
if(hchild[now]) dfs2(now,hchild[now],tp);
while(p)
{
if(to[p]==father||to[p]==hchild[now])
{p=next[p];continue;}
dfs2(now,to[p],to[p]);
p=next[p];
}
}
int main()
{
int temp1,temp2;
clear();
scanf("%d",&n);
for(int i=1;i<=n+1;i++)
{
scanf("%d%d",&temp1,&temp2);
addedge(temp1,temp2);
addedge(temp2,temp1);
}
dfs1(1,1,1);
dfs2(1,1,1);
}
评论