社区讨论

求助,第4个点疯狂RE

P3258[JLOI2014] 松鼠的新家参与者 6已保存回复 18

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
18 条
当前快照
1 份
快照标识符
@mi6wcw3r
此快照首次捕获于
2025/11/20 11:53
4 个月前
此快照最后确认于
2025/11/20 15:00
4 个月前
查看原帖
RT 交了好多次 身败名裂
是lca做法
太惨了。。
CPP
#include<cstdio>
#include<cstring>
#define N 500000+5
#define inf 0x7f7f7f7f
#define ll long long
using namespace std;

inline ll read(){
	ll e=0,ch=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')ch=-1;c=getchar();}
	while(c>='0'&&c<='9'){e=e*10+(c-48);c=getchar();}
	return e*ch;
}

inline void write(ll x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

ll n,m,ans,a,b,cnt;
ll head[N],list[N],cf[N],dep[N];
ll f[N][25];

struct node{
	ll v,nex;
}e[N<<1];

inline void swap(ll &a,ll &b){
	a^=b^=a^=b;
}

inline void add(ll u,ll v){
	cnt++;
	e[cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void dfs(ll u,ll fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(register ll i=1;i<=24;++i) f[u][i]=f[f[u][i-1]][i-1];
	for(register ll i=head[u];i;i=e[i].nex){
		ll v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
	}
}

inline ll lca(ll a,ll b){
	if(dep[a]>dep[b]) swap(a,b);
	for(register ll i=24;i>=0;--i){
		if(dep[a]>dep[f[b][i]]) continue;
		b=f[b][i];
	}
	if(a==b) return a;
	for(register ll i=24;i>=0;--i){
		if(f[a][i]==f[b][i]) continue;
		a=f[a][i];
		b=f[b][i];
	}
	return f[a][0];
}

void solve(ll u,ll fa){
	for(register int i=head[u];i;i=e[i].nex){
		ll v=e[i].v;
		if(v==fa) continue;
		solve(v,u);
		cf[u]+=cf[v];
	}
}

int main(){
	n=read();
	for(register int i=1;i<=n;++i) list[i]=read();
	for(register int i=1;i<n;++i){
		a=read();b=read();
		add(a,b);add(b,a);
	}
	dfs(1,0);
	ll ab;
	for(register int i=1;i<n;++i){
		a=list[i],b=list[i+1];
		ab=lca(a,b);
		cf[a]++;
		cf[f[b][0]]++;
		cf[ab]--;
		cf[f[ab][0]]--;
	}
	solve(1,0);
	for(register int i=1;i<=n;++i) write(cf[i]),puts("");
	return 0;
}

回复

18 条回复,欢迎继续交流。

正在加载回复...