提出 #582832

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define N 100100
using namespace std;
int p[N][20],dep[N],far[N],add[N],id[N];
vector<int> v[N];
int go(int a,int x){
	int r=a;
	for(int i=0;i<20;i++){
		if(x&(1<<i)) r=p[r][i];
	}
	return r;
}
int lca(int a,int b){
	if(dep[a]>dep[b]){
		a=go(a,dep[a]-dep[b]);
	}
	else{
		b=go(b,dep[b]-dep[a]);
	}
	if(a==b) return a;
	for(int i=19;i>=0;i--){
		if(p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
	}
	return p[a][0];
}
bool cmp(int i,int j){
	return id[p[i][0]]<id[p[j][0]]||p[i][0]==p[j][0]&&i<j;
}
int main(){
	int n;
	long long ans=0;
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d",&p[i][0]);
	p[1][0]=1;
	for(int i=1;i<20;i++){
		for(int j=1;j<=n;j++){
			p[j][i]=p[p[j][i-1]][i-1];
		}
	}
	dep[1]=0;
	for(int i=2;i<=n;i++){
		dep[i]=dep[p[i][0]]+1;
		far[i]=dep[i];
		v[dep[i]].push_back(i);
	}
	v[0].push_back(1);
	for(int i=n;i>1;i--){
		far[p[i][0]]=max(far[i],far[p[i][0]]);
		add[dep[i]]++;
		add[far[i]+1]--;
	}
	for(int i=1;i<=n&&!v[i].empty();i++){
		sort(v[i].begin(),v[i].end(),cmp);
		for(int j=0;j<v[i].size();j++) id[v[i][j]]=j;
		add[i]+=add[i-1];
		ans+=dep[v[i].front()]+dep[v[i-1].back()]-2*dep[lca(v[i].front(),v[i-1].back())];
		ans+=2*(add[i]-i);
	}
	printf("%lld\n",ans);
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

ジャッジ結果