Trancy

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);

}


评论