| 6867 | Tree |
const int maxn = 5e5+10;
int sz[maxn];
vector<int>e[maxn];
void dfs(int x,int f){
sz[x] = 1;
for(auto v:e[x]){
if(v!=f){
dfs(v,x);
sz[x]+=sz[v];
}
}
}
ll now = 0;
ll mx = 0;
int n;
void solve(int x,int f){
now+=n-sz[x];
mx=max(mx,now);
for(auto v:e[x]){
if(v!=f){
solve(v,x);
}
}
now-=n-sz[x];
}
int main(){
#ifdef LOCAL
freopen("D:/input.txt","r",stdin);
//freopen("D:/output.txt","w",stdout);
#endif
int t;scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i =1;i<=n;i++)e[i].clear();
for(int i =2;i<=n;i++){
int fa;scanf("%d",&fa);
e[fa].push_back(i);
}
mx = 0,now= 0;
dfs(1,1);
ll ans = 0;
for(int i=1;i<=n;i++)ans+=sz[i];
solve(1,1);
printf("%lld\n",ans + mx);
}
}| 6868 | Absolute Math |
| 6869 | Slime and Stones |
const int maxn = 5e5+10;
int sg[120][120];
int SG(int a,int b,int k){
if(abs(a-b)<=k)return 1;
else if(sg[a][b])return sg[a][b];
else if(a==0&&b==0)return 2;
else if(a==0||b==0)return 1;
int ans1=0,ans2=0,ans;
for(int i=1;i<=a;++i){
ans=SG(a-i,b,k);
if(ans==1)ans1++;
if(ans==2)ans2++;
}
for(int i=1;i<=b;++i){
ans=SG(a,b-i,k);
if(ans==1)ans1++;
if(ans==2)ans2++;
}
for(int i=1;i<=a;++i){
for(int j=1;j<=b;++j){
if(abs(i-j)<=k){
ans=SG(a-i,b-j,k);
if(ans==1)ans1++;
if(ans==2)ans2++;
}
}
}
if(ans2)sg[a][b]=1;
else sg[a][b]=2;
return sg[a][b];
}
int main(){
#ifdef LOCAL
freopen("D:/input.txt","r",stdin);
//freopen("D:/output.txt","w",stdout);
#endif
// for(int i=1;i<=100;++i){
// for(int j=i;j<=100;++j){
// int ans=SG(i,j,2);
// if(ans==2)printf("%d %d %d\n",i,j,ans);
// }
// }
// ll k=1;
// ll d=4+k*k,n=10;
// int a=floor(0.5*(sqrt(d)+2-k)*(n));
// int b=floor(0.5*(sqrt(d)+2+k)*(n));
// printf("%d %d\n",a,b);
times{
int a,b,k;
scanf("%d%d%d",&a,&b,&k);
if(a>b)swap(a,b);
k++;
ll d=4ll+1ll*k*k;
int l=1,r=b,ans;
while(l<r){
int tmp=floor(0.5*(sqrt(d)+2-k)*(l+r>>1));
if(tmp>=a){
ans=(l+r)>>1;
r=(l+r)>>1;
if(tmp==a)break;
}
else l=((l+r)>>1)+1;
}
ll A=floor(0.5*(sqrt(d)+2-k)*(ans));
ll B=floor(0.5*(sqrt(d)+2+k)*(ans));
if(A==a&&B==b)printf("0\n");
else printf("1\n");
}
}