社区讨论
求助,第4个点疯狂RE
P3258[JLOI2014] 松鼠的新家参与者 6已保存回复 18
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 18 条
- 当前快照
- 1 份
- 快照标识符
- @mi6wcw3r
- 此快照首次捕获于
- 2025/11/20 11:53 4 个月前
- 此快照最后确认于
- 2025/11/20 15:00 4 个月前
RT 交了好多次 身败名裂
是lca做法
太惨了。。
CPP是lca做法
太惨了。。
#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 条回复,欢迎继续交流。
正在加载回复...