社区讨论
大数据读入会有问题?
P3258[JLOI2014] 松鼠的新家参与者 5已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi85uxxs
- 此快照首次捕获于
- 2025/11/21 09:07 4 个月前
- 此快照最后确认于
- 2025/11/21 09:07 4 个月前
T了两个点,数据下出来后发现大数据没法读入,求解
CPP#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int a,b,n,cnt=0,ans[1000000]={0},head[1000000]={0},jl[1000000]={0},p[1000000]={0};
int mark[1000000]={0},grand[300010][30]={0},deep[1000000]={0};
struct node{
int to,next;
}tu[2000010];
void dfs(int x){
for(int i=1;(1<<i)<=deep[x];i++)
grand[x][i]=grand[ grand[x][i-1] ][ i-1 ];
for(int i=head[x];i;i=tu[i].next){
if(tu[i].to==grand[x][0]) continue;
p[x]=1;
grand[tu[i].to][0]=x;
deep[tu[i].to]=deep[x]+1;
dfs(tu[i].to);
}
}
int lca(int x,int y){
if(deep[x]>deep[y]) swap(x,y);
int h=deep[y]-deep[x];
for(register int i=0;(1<<i)<=h;++i){
if(h&(1<<i))
y=grand[y][i];
}
if(x==y) return x;
for(register int i=log2(n);i>=0;--i){
if(grand[x][i]!=grand[y][i]){
x=grand[x][i];
y=grand[y][i];
}
}
return grand[x][0];
}
void up(int x,int flag){
flag+=mark[x];
mark[x]=0;
ans[x]+=flag;
if(grand[x][0])
up(grand[x][0],flag);
}
inline void add(int u,int v){
++cnt;
tu[cnt].to=v;
tu[cnt].next=head[u];
head[u]=cnt;
}
int main(){
cin>>n;
for(register int i=1;i<=n;++i)
cin>>jl[i];
for(register int i=1;i<n;++i){
cin>>a>>b;
add(a,b);
add(b,a);
}
deep[1]=0;
dfs(1);
for(register int i=1;i<n;++i){
++mark[jl[i]];
++mark[jl[i+1]];
int t=lca(jl[i],jl[i+1]);
--mark[t];
--mark[grand[t][0]];
--ans[jl[i]];
}
for(register int i=1;i<=n;++i){
if(!p[i])
up(i,0);
}
++ans[jl[1]],--ans[jl[n]];
for(register int i=1;i<=n;++i)
cout<<ans[i]<<endl;
return 0;
}
回复
共 9 条回复,欢迎继续交流。
正在加载回复...