【题解】P3258松鼠的新家

【题解】[P3258 JLOI2014]松鼠的新家

树链剖分板子题。

总结一点容易写错的地方吧：

if(d[top[u]]<d[top[v]]) swap(u,v);注意是\(top\)。
在\(dfs2\)中，if(e[t].to!=r[now]&&e[t].to!=son[now])注意\(r[now]\)而不是\(last\)

#include<bits/stdc++.h>

using namespace std;

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)

#define Max(a,b) ((a)<(b)?(b):(a))

#define Min(a,b) ((a)<(b)?(a):(b))

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lowbit(x) ((x)&(-(x)))

TMP inline ccf qr(ccf b){

    char c=getchar();

    int q=1;

    ccf x=0;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

const int maxn=300005;

struct E{

    int to,nx;

}e[maxn<<1];

int cnt,n;

int head[maxn];

int mov[maxn];

int toseg[maxn];

int siz[maxn];

int son[maxn];

int top[maxn];

int r[maxn];

int d[maxn];

int seg[maxn];

inline void add(int to,int fr,bool f){

    e[++cnt]=(E){to,head[fr]};

    head[fr]=cnt;

    if(f)

	add(fr,to,0);

}

void dfs1(int now,int last){

    d[now]=d[last]+1;

    r[now]=last;

    siz[now]=1;

    ERP(t,now){

	if(e[t].to!=last){

	    dfs1(e[t].to,now);

	    siz[now]+=siz[e[t].to];

	    if(siz[e[t].to]>siz[son[now]])

		son[now]=e[t].to;

	}

    }

}

void dfs2(int now,int last){

    top[now]=last;

    toseg[now]=++toseg[0];

    if(son[now])

	dfs2(son[now],last);

    ERP(t,now)

	if(e[t].to!=r[now]&&e[t].to!=son[now])

	    dfs2(e[t].to,e[t].to);

}

inline void basic_add(int x,int tag){

    for(register int t=x;t<=n;t+=lowbit(t))seg[t]+=tag;

}

inline void inv_add(int l,int r,int tag){

    basic_add(l,tag);basic_add(r+1,-tag);

}

inline void upd(int u,int v){

    while(top[u]!=top[v]){

	if(d[top[u]]<d[top[v]]) swap(u,v);

	inv_add(toseg[top[u]],toseg[u],1);

	u=r[top[u]];

    }

    if(d[u]<d[v]) swap(u,v);

    inv_add(toseg[v],toseg[u],1);

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);

    RP(t,1,n) mov[t]=qr(1);

    for(register int t=2,t1,t2;t<=n;++t)

	t1=qr(1),t2=qr(1),add(t1,t2,1);

    dfs1(1,0);

    dfs2(1,1);

    RP(t,1,n-1)

	upd(mov[t],mov[t+1]);

    RP(t,2,n)

	inv_add(toseg[mov[t]],toseg[mov[t]],-1);

    RP(t,1,n){

	register int ans=0;

	for(register int i=toseg[t];i;i-=lowbit(i))

	    ans+=seg[i];

	printf("%d\n",ans);

    }

    return 0;

}

巴特西

【题解】P3258松鼠的新家

【题解】[P3258 JLOI2014]松鼠的新家

最新文章

热门文章