#5
Division into Two
题面
为方便，令 \(A>B\)。，如果存在 \(a_{i+2}-a_i<B\)，即存在三个数，两两之间的差小于 \(B\)，显然无解。
考虑dp，令 \(f_i\) 表示以第 \(i\) 个数为 \(A\) 集合选择的最后一个数的方案数，考虑转移过来的点 \(j\) 要满足的要求。
- \(a_i-a_j\ge a\)
- \(\forall x,y\in [j,i]\text{且}x<y,a_y-a_x\ge B\)
可以发现 \(j\) 能选的范围是一个区间。第一个要求限制了 \(j\) 能选的最大值，第二个操作限制了 \(j\) 能选的最小值，维护一下前缀和就可以了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,mod=1e9+7;
int n,a,b,val[N],f[N],s[N];
void solve(){
read(n),read(a),read(b);
if(a<b){
swap(a,b);
}
for(int i=1;i<=n;i++){
read(val[i]);
}
for(int i=1;i<=n-2;i++){
if(val[i+2]-val[i]<b){
puts("0");
return;
}
}
f[0]=s[0]=1;
for(int i=1,p=0,q=0;i<=n;i++){
while(q<i&&val[i]-val[q+1]>=a){
q++;
}
if(p<=q){
f[i]=(f[i]+s[q]-(p?s[p-1]:0)+mod)%mod;
}
s[i]=(s[i-1]+f[i])%mod;
if(i>1&&val[i]-val[i-1]<b){
p=i-1;
}
}
int ans=0;
for(int i=n;i>=0;i--){
ans=(ans+f[i])%mod;
if(i<n&&val[i+1]-val[i]<b){
break;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Maximize Mex
题面
删人难做，转倒序加人。
如果已知有哪些人存在，怎么做。将人对应的权值和对应的社团连边，显然是一张二分图，剩下的类似于连续攻击游戏一样做就行了，从小的权值到大的权值，逐一匹配，如果匹配不上，则说明答案为当前权值。加一条边的操作，直接在匹配后的图上加边继续匹配即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e3+10;
int n,m,val[N],p[N],vis[N],ad[N],cnt,couple[N],ans,Ans[N];
vector<int>e[N];
int find(int u,int T){
if(vis[u]==T){
return 0;
}
vis[u]=T;
for(auto v:e[u]){
if(couple[v]==-1||find(couple[v],T)){
couple[v]=u;
return 1;
}
}
return 0;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
read(val[i]);
}
for(int i=1;i<=n;i++){
read(p[i]);
}
for(int i=1;i<=m;i++){
couple[i]=-1;
}
read(cnt);
for(int i=1;i<=cnt;i++){
read(ad[i]);
vis[ad[i]]=1;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
e[val[i]].pb(p[i]);
}
}
for(int i=cnt;i;i--){
for(int j=0;j<=n;j++){
vis[j]=-1;
}
while(find(ans,ans)){
ans++;
}
Ans[i]=ans;
e[val[ad[i]]].pb(p[ad[i]]);
}
for(int i=1;i<=cnt;i++){
write_endl(Ans[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[BalkanOI2011] timeismoney | 最小乘积生成树
题面
正睿出了道类似的，但因为数据范围不同且为仙人掌，做法不同。
对于本题，设 \(S\) 为生成树的边集，将 \(\sum\limits_{i\in S}a_i\) 和 \(\sum\limits_{i\in S} b_i\) 看作这颗生成树的二维坐标 \((x,y)\)，放到平面上，一个非常容易得到的结论是，\(x\times y\) 的最小值，一定在这些点的集合的凸壳上。
求这个凸壳的时候，我们发现有两个点特别好找，一个是 \(x\) 最小的点，另一个是 \(y\) 最小的点。以 \(a\) 为边权得到的最小生成树是 \(x\) 最小的点，令其为 \(A\)；以 \(b\) 为边权得到的最小生成树是 \(y\) 最小的点，令其为 \(B\)。
接下来，我们找线段 \(AB\) 下面距离 \(AB\) 最远的点，令其为 \(C\)。显然距离最远也就表示 \(S_{\triangle abc}\) 面积最大。学过计算几何的都知道，\(S_{\triangle abc}\) 在这里有另一种计算方式，\(S_{\triangle abc}=-\frac{\overrightarrow{AB}\times \overrightarrow{AC}}{2}\)，即我们要求 \(\overrightarrow{AB}\times \overrightarrow{AC}\) 的最小值。
拆开 \(\overrightarrow{AB}\times \overrightarrow{AC}\) 得:
\[\overrightarrow{AB}\times \overrightarrow{AC}\begin{aligned}&=(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)\\&=(x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A-(y_B-y_A)x_A\end{aligned}
\]
因为后两项是常数，所以我们只需要使得前两项的和最小，以 \((x_B-x_A)b_i+(y_A-y_B)a_i\) 为边权，跑最小生成树就可以找到点 \(C\)。分治下去，可以得到凸壳上的点，在凸壳上找到最小值即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,M=3e5+10,inf=1e9;
int n,m;
ll ans_num;
namespace dsu{
int fa[N];
void init(int mx){
for(int i=1;i<=mx;i++){
fa[i]=i;
}
}
int getfa(int x){
if(fa[x]!=x){
fa[x]=getfa(fa[x]);
}
return fa[x];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
if(u!=v){
fa[v]=u;
}
}
}
struct edge{
int u,v,w,a,b;
}e[M];
struct point{
int x,y;
}ans;
point operator -(point x,point y){
return (point){x.x-y.x,x.y-y.y};
}
int cross(point x,point y){
return x.x*y.y-x.y*y.x;
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
point kruskal(){
point res=(point){0,0};
sort(e+1,e+m+1,cmp);
dsu::init(n);
int cnt=0;
for(int i=1;i<=m;i++){
int u=dsu::getfa(e[i].u),v=dsu::getfa(e[i].v),a=e[i].a,b=e[i].b;
if(u==v){
continue;
}
dsu::merge(u,v);
res.x+=a;
res.y+=b;
cnt++;
if(cnt==n-1){
break;
}
}
ll Ans=1ll*ans.x*ans.y,Res=1ll*res.x*res.y;
if(Ans>Res||(Ans==Res&&ans.x>res.x)){
ans=res;
}
return res;
}
void work(point A,point B){
for (int i=1;i<=m;++i){
e[i].w=e[i].b*(B.x-A.x)+e[i].a*(A.y-B.y);
}
point C=kruskal();
if(cross(B-A,C-A)>=0){
return;
}
work(A,C);
work(C,B);
}
void solve(){
ans=(point){inf,inf};
read(n),read(m);
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v),read(e[i].a),read(e[i].b);
e[i].u++;
e[i].v++;
}
for(int i=1;i<=m;i++){
e[i].w=e[i].a;
}
point A=kruskal();
for(int i=1;i<=m;i++){
e[i].w=e[i].b;
}
point B=kruskal();
work(A,B);
write_space(ans.x),write_endl(ans.y);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
对于正睿的题，将图上的环全部分开考虑，因为是仙人掌，所以环与环之间不会相互影响。枚举一个环上割掉哪条边会产生一个点，求出这些点的凸包，两个环的答案加和相当于做一遍闵可夫斯基和。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=6e5+10;
int top=0;
ll ans=LONG_LONG_MAX;
struct point{
int x,y;
}stk[N];
point operator +(point x,point y){
return (point){x.x+y.x,x.y+y.y};
}
point operator -(point x,point y){
return (point){x.x-y.x,x.y-y.y};
}
ll operator * (point x,point y){
return 1ll*x.x*y.y-1ll*x.y*y.x;
}
struct node{
vector<point>P;
void Sort(){
sort(P.begin(),P.end(),[](point x,point y){
return x.x==y.x?x.y<y.y:x.x<y.x;
});
}
void build(int opt=0){
if(opt==0){
Sort();
}
top=0;
for(auto x:P){
if(!top){
stk[top=1]=x;
}
while(top>1&&((x-stk[top])*(stk[top]-stk[top-1])>=0ll)){
top--;
}
stk[++top]=x;
}
P=vector<point>(stk+1,stk+top+1);
}
}p[N];
node operator +(node x,node y){
int sizx=x.P.size(),sizy=y.P.size();
int nowx=1,nowy=1,top=0;
top=1;
stk[top]=x.P[0]+y.P[0];
for(int i=sizx-1;i;i--){
x.P[i]=x.P[i]-x.P[i-1];
}
for(int i=sizy-1;i;i--){
y.P[i]=y.P[i]-y.P[i-1];
}
while(nowx<sizx&&nowy<sizy){
if(x.P[nowx]*y.P[nowy]>=0){
++top;
stk[top]=stk[top-1]+x.P[nowx];
nowx++;
}
else{
++top;
stk[top]=stk[top-1]+y.P[nowy];
nowy++;
}
}
while(nowx<sizx){
++top;
stk[top]=stk[top-1]+x.P[nowx++];
}
while(nowy<sizy){
++top;
stk[top]=stk[top-1]+y.P[nowy++];
}
node z;
z.P=vector<point>(stk+1,stk+top+1);
z.build(1);
return z;
}
auto solve(int l,int r){
if(l==r){
return p[l];
}
int mid=(l+r)>>1;
return solve(l,mid)+solve(mid+1,r);
}
int n,m,a[N],b[N],dfn[N],low[N],sta[N],tp,cnt,col_num;
vector<int>e[N],col[N],id[N];
map<int,int>edge[N];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
sta[++tp]=u;
for(auto v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){
col[++col_num].pb(u);
while(1){
int x=sta[tp--];
col[col_num].pb(x);
if(x==v){
break;
}
}
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1,u,v;i<=m;i++){
read(u),read(v);
read(a[i]),read(b[i]);
e[u].pb(v);
e[v].pb(u);
edge[u][v]=edge[v][u]=i;
}
tp=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=col_num;i++){
int siz=col[i].size();
for(int j=0;j<siz-1;j++){
id[i].pb(edge[col[i][j]][col[i][j+1]]);
}
id[i].pb(edge[col[i].front()][col[i].back()]);
}
for(int i=1;i<=col_num;i++){
int suma=0,sumb=0;
for(auto x:id[i]){
suma+=a[x];
sumb+=b[x];
}
for(auto x:id[i]){
p[i].P.pb(point{suma-a[x],sumb-b[x]});
}
p[i].build();
}
auto res=solve(1,col_num);
for(auto x:res.P){
ans=min(ans,1ll*x.x*x.y);
}
write_endl(ans);
return 0;
}
[CCO2021] Travelling Merchant
题面
定义 \(f_u\) 表示从 \(u\) 出发最小的初始资产，可以得到 \(f_u=\min(f_u,\max(r(u,v),f_v-p(u,v))\)。但因为图上有环，此时我们不能直接转移。可以发现原图上出度为 \(0\) 的点显然无解，因为到不了环上。先类似于拓扑排序，去掉这些到不了环上的点和边。
对于剩下的边，从大到小考虑，如果当且边 \((u,v,r,p)\) 没被删除，那么它可以直接影响 \(u\)，\(f_u=\min(f_u,r)\)，令出度 \(deg_u-1\)，如果 \(deg_u=0\)，再做一遍类似于拓扑排序的操作转移。可以这样做的原因是，边是从大到小处理的，如果当前边没被处理到，那么后面处理的边的 \(r\) 值均小于当前 \(r\) 值，不会影响到经过当前边的最后答案。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,inf=1e9;
struct edge{
int u,v,r,p,id;
}e[N];
bool cmp(edge x,edge y){
return x.r>y.r;
}
int n,m,deg[N],ans[N],vis[N],head[N],tot=1;
queue<int>q;
struct node{
int v,r,p,nxt,id;
}G[N<<1];
void add(int u,int v,int r,int p,int id){
G[++tot].v=v;
G[tot].r=r;
G[tot].p=p;
G[tot].id=id;
G[tot].nxt=head[u];
head[u]=tot;
}
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v),read(e[i].r),read(e[i].p);
e[i].id=i;
deg[e[i].u]++;
add(e[i].v,e[i].u,e[i].r,e[i].p,e[i].id);
}
for(int i=1;i<=n;i++){
if(!deg[i]){
q.push(i);
}
ans[i]=inf;
}
sort(e+1,e+m+1,cmp);
while(!q.empty()){
int v=q.front();
q.pop();
for(int j=head[v];j;j=G[j].nxt){
if(vis[G[j].id]){
continue;
}
vis[G[j].id]=1;
int u=G[j].v,r=G[j].r,p=G[j].p;
deg[u]--;
if(!deg[u]){
q.push(u);
}
}
}
for(int i=1;i<=m;i++){
if(!vis[e[i].id]){
vis[e[i].id]=1;
ans[e[i].u]=min(ans[e[i].u],e[i].r);
deg[e[i].u]--;
if(!deg[e[i].u]){
q.push(e[i].u);
}
}
while(!q.empty()){
int v=q.front();
q.pop();
for(int j=head[v];j;j=G[j].nxt){
if(vis[G[j].id]){
continue;
}
vis[G[j].id]=1;
int u=G[j].v,r=G[j].r,p=G[j].p;
ans[u]=min(ans[u],max(r,ans[v]-p));
deg[u]--;
if(!deg[u]){
q.push(u);
}
}
}
}
for(int i=1;i<=n;i++){
if(ans[i]==inf){
write_space(-1);
}
else{
write_space(ans[i]);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;>
}
Triameter
题面
先考虑 \(O(nq\log^2 n)\) 的做法怎么做。因为是最短路，所以最多经过一条权值为 \(x\) 的边，令 \(g_a\) 表示从点 \(a\) 到距离它最近的叶子的距离。从 \(u\) 到 \(v\) 的距离可以表示为 \(\min(dep_u+dep_v-2\times dep_{lca_{(u,v)}},g_u+g_v+x)\)。使用点分治统计经过分治中心的路径的答案。
分类讨论哪个更大。
-
\((dep_u-dep_{lca_{(u,v)}})+(dep_v-dep_{lca_{(u,v)}})\le g_u+g_v+x\)，
移项得 \(dep_u-dep_{lca_{(u,v)}}-g_u\le -(dep_v-dep_{lca_{(u,v)}}-g_v)+x\)。用一个数据结构对后面部分的位置做一个对 \(dep_v-dep_{lca_{(u,v)}}\) 取 \(\max\) 的操作。询问时只需要求一个后缀 \(\max\) 即可。 -
移项得到 \(dep_u-dep_{lca_{(u,v)}}-g_u\ge -(dep_v-dep_{lca_{(u,v)}}-g_v)+x\)。对后面部分做一个对 \(g_v\) 取 \(\max\) 的操作。询问时查询前缀 \(\max\)。
显然这个 \(nq\log^2 n\) 的做法是过不去的。我们发现在 \(g\) 确定时，可能影响我们答案的只有 \(dep\) 最大的点。令 \(f_{u,i}\) 表示，在 \(u\) 子树内，\(g_v=i\) 的 \(dep_v\) 最大的 \(v\)。注意到 \(u\) 子树内的 \(g\) 不会超过 \(u\) 子树内的最长链，我们可以想到长链剖分。
\(u\) 继承长儿子得到的 \(f\)，剩下的儿子暴力合并。从长儿子转移过来的可以用 \(\min(f_{large_u,i}-dep_u,i+g_u+x)\) 更新答案。从其它儿子转移过来的可以用 \(\min(f_{v,i}+f_{u,j}-2\times dep_u,i+j+x)\) 更新答案。为了保证复杂度，我们令它只进行有效更新，这样答案最多更新 \(n\) 次，总复杂度仍为 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
int dep[N],mxlen[N],fa[N],top[N],large[N],n,val,ans;
vector<int>e[N];
void make_tree(int u,int father){
fa[u]=father;
dep[u]=dep[father]+1;
for(auto v:e[u]){
if(v==father){
continue;
}
make_tree(v,u);
mxlen[u]=max(mxlen[u],mxlen[v]+1);
if(!large[u]||mxlen[v]>mxlen[large[u]]){
large[u]=v;
}
}
}
vector<int>f[N];
int g[N];
queue<int>q;
void dfs(int u){
if(large[u]){
dfs(large[u]);
swap(f[u],f[large[u]]);
}
for(int i=max(0,ans-val-g[u]+1);i<f[u].size()&&f[u][i]-dep[u]>ans;i++){
ans=max(ans,min(i+g[u]+val,f[u][i]-dep[u]));
}
f[u].resize(max(g[u]+1,(int)f[u].size()));
f[u][g[u]]=max(f[u][g[u]],dep[u]);
for(auto v:e[u]){
if(v==fa[u]||v==large[u]){
continue;
}
dfs(v);
for(int i=0;i<f[v].size();i++){
for(int j=max(0,ans-val-i+1);j<f[u].size()&&f[u][j]+f[v][i]-2*dep[u]>ans;j++){
ans=max(ans,min(i+j+val,f[u][j]+f[v][i]-2*dep[u]));
}
}
f[u].resize(max(f[u].size(),f[v].size()));
for(int i=0;i<f[v].size();i++){
f[u][i]=max(f[u][i],f[v][i]);
}
f[v].clear();
}
}
void solve(){
ans=0;
read(val);
for(int i=1;i<=n;i++){
vector<int>().swap(f[i]);
}
dfs(1);
write_space(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
memset(g,-1,sizeof(g));
read(n);
for(int u=2,v;u<=n;u++){
read(v);
e[u].pb(v);
e[v].pb(u);
}
for(int i=1;i<=n;i++){
if(e[i].size()>1){
continue;
}
q.push(i);
g[i]=0;
}
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:e[u]){
if(g[v]==-1){
g[v]=g[u]+1;
q.push(v);
}
}
}
make_tree(1,0);
int q;
read(q);
while(q--){
solve();
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}