Portal
Preface
Once a year, the cedar trees growing on the mountains bear fruit again.
The next day, the cedar tree grew into a towering tree full of cedars.
Find the growth cycle of cedar tree
The whole work is to solve the problem.
I'll keep struggling for 3 hours, commemorate it.
Yes, my submission alone accounts for three pages.
Brief description of the title
Give a tree and query a node\(k\)-cousin。
Question explanation
Basic ideas
Although there are many better practices, we consider segment tree merging.
Create a weight segment tree in each node to maintain the number of nodes at each depth in the subtree.
Take the query offline, perform dfs on the entire tree, merge the segment tree of each subtree into the segment tree of the node, and then process the inquiry of the node.
Here you need to convert the query into the original query node\(k\)-father's\(k\)-son number one.
beg\(k\)-father can use multiplication.
So we can write the following code:
#include <cstdio>
#include <vector>
#define N 1000005
int n,q,ans[N],fa[N][21],rt[N];
int hed[N],tal[N],nxt[N],cnte;
void adde(int u,int v) {tal[++cnte]=v,nxt[cnte]=hed[u],hed[u]=cnte;}
struct query {int id,k;};
std::vector<query> a[N];
struct sgt
{
#define mid (lb+rb>>1)
#define pushup(x) d[x]=d[ls[x]]+d[rs[x]]
int d[N<<5],ls[N<<5],rs[N<<5],idx;
void modify(int &x,int t,int lb,int rb)
{
if(!x) x=++idx;
d[x]++;
if(lb==rb) return;
if(t<=mid) modify(ls[x],t,lb,mid);
else modify(rs[x],t,mid+1,rb);
}
int query(int x,int t,int lb,int rb)
{
if(!x) return 0;
if(lb==rb) return d[x];
if(t<=mid) return query(ls[x],t,lb,mid);
else return query(rs[x],t,mid+1,rb);
}
int merge(int x,int y,int lb,int rb)
{
if(!x||!y) return x+y;
if(lb==rb) {d[x]+=d[y];return x;}
ls[x]=merge(ls[x],ls[y],lb,mid);
rs[x]=merge(rs[x],rs[y],mid+1,rb);
pushup(x);return x;
}
#undef mid
#undef pushup
} tr;
void dfs(int x,int f,int dep)
{
(rt[x],dep,1,n);
for(int i=hed[x];i;i=nxt[i]) if(tal[i]!=f)
dfs(tal[i],x,dep+1),rt[x]=(rt[x],rt[tal[i]],1,n);
for(int i=0;i<a[x].size();i++)
ans[a[x][i].id]=(rt[x],dep+a[x][i].k,1,n)-1;
}
main()
{
scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++) scanf("%d",&fa[i][0]),adde(fa[i][0],i);
for(int i=1;i<=20;i++) for(int j=2;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=q;i++)
{
int u,k;
scanf("%d%d",&u,&k);
int d=0;
for(int j=20;j>=0;j--)
if(d+(1<<j)<=k) u=fa[u][j],d+=1<<j;
if(u) a[u].push_back({i,k});
}
dfs(1,0,1);
for(int i=1;i<=q;i++) printf("%d ",ans[i]);
}
Like this.
optimization
If you wrote the above code as we just thought, then congratulations, you can get\(40\)Good results for scores.
So we need to optimize.
Since the remaining points are MLE, the space needs to be optimized.
First, notice that the array of line segment trees is very large, because each point has a line segment tree. However, when we merge statistical answers from segment trees, when the answers of a node are merged into the parent node, the segment trees of this node will no longer be used. So we recycle the nodes on this line segment tree. In this way, the space of the segment tree only needs to be opened to\(4e6\)。
So I got a line segment tree:
struct sgt
{
#define mid (lb+rb>>1)
int d[N<<2],ls[N<<2],rs[N<<2],idx;
int st[M],tp; //Recycle
void modify(int &x,int t,int lb,int rb)
{
if(!x) x=tp?st[tp--]:++idx; //Use the previously recycled space
d[x]++;
if(lb==rb) return;
if(t<=mid) modify(ls[x],t,lb,mid);
else modify(rs[x],t,mid+1,rb);
}
int query(int x,int t,int lb,int rb)
{
if(!x) return 0;
if(lb==rb) return d[x];
if(t<=mid) return query(ls[x],t,lb,mid);
return query(rs[x],t,mid+1,rb);
}
int merge(int x,int y,int lb,int rb)
{
if(!x||!y) return x|y;
d[x]+=d[y];
if(lb<rb)
ls[x]=merge(ls[x],ls[y],lb,mid),
rs[x]=merge(rs[x],rs[y],mid+1,rb);
d[y]=ls[y]=rs[y]=0,st[++tp]=y; //Recycle space
return x;
}
#undef mid
} tr;Secondly, we opened\(1e6\)indivualvectorTo store the inquiry, the space consumed in this way is unacceptable, so the storage method of the inquiry needs to be changed.
A forward star approach can be used:
int qh[N]; //Chapter head
int qnxt[N]; //Number of next inquiry
struct query
{
int v,k; //v:u's k-father
} a[N];
void addq(int x)
{
qnxt[x]=qh[a[x].v];
qh[a[x].v]=x;
}Then we saw that the multiplication array used to find k-father also takes up a lot of space, so we switched to tree section.
int dep[N],son[N],siz[N],top[N],dfn[N],li[N],id;
void dfs1(int x) //Normal tree section
{
siz[x]=1,dep[x]=dep[fa[x]]+1;
for(int i=hed[x];i;i=nxt[i])
if(!siz[tal[i]])
{
dfs1(tal[i]);
siz[x]+=siz[tal[i]];
if(siz[tal[i]]>siz[son[x]])
son[x]=tal[i];
}
}
void dfs2(int x,int tp) //Normal number anatomy
{
li[dfn[x]=++id]=x,top[x]=tp;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=hed[x];i;i=nxt[i])
if(!top[tal[i]])
dfs2(tal[i],tal[i]);
}
int anc(int u,int k)
{
int v=u;
while(v&&dep[u]-dep[top[v]]<k)
v=fa[top[v]];
if(!v) return 0; //No k-father
/*
Example: u=8,k=4,dep[8]=7
Jump to heavy chain 1-6
1-2-3-4-5-6
^ ^ v
top kfa
: : : : : : : : : : : : : : :
dep[3]=dep[u]-k
dfn[1]+dep[3]-dep[1]=dfn[3]
li[dfn[3]]=3
*/
return li[dfn[top[v]]+dep[u]-k-dep[top[v]]];
}Like this.
Ultimate Optimization
If you use the above method to optimize, then congratulations, you can no longer MLE and get\(76\)Divide to\(92\)Good results with varying points.Of course, it's fine if your writing constant is smaller and the card is over.
Why can't AC?
Let's look at the part of the initial code that calls the segment tree:
rt[x]=(rt[x],rt[tal[i]],1,n);
The value range of the segment tree is\(n\)。
However, our segment tree maintains depth.
So the value range should be the maximum value of depth.
Code
#include <cstdio>
#define N 1000002
int n,q,md,ans[N],fa[N],rt[N];
int hed[N],tal[N],nxt[N],cnte;
void adde(int u,int v) {tal[++cnte]=v,nxt[cnte]=hed[u],hed[u]=cnte;}
int qh[N],qnxt[N];
int av[N],ak[N];
void addq(int x) {qnxt[x]=qh[av[x]],qh[av[x]]=x;}
int dep[N],son[N],siz[N],top[N],dfn[N],li[N],id;
void dfs1(int x)
{
siz[x]=1,dep[x]=dep[fa[x]]+1;
if(dep[x]>md) md=dep[x];
for(int i=hed[x];i;i=nxt[i]) if(!siz[tal[i]])
{
dfs1(tal[i]),siz[x]+=siz[tal[i]];
if(siz[tal[i]]>siz[son[x]]) son[x]=tal[i];
}
}
void dfs2(int x,int tp)
{
li[dfn[x]=++id]=x,top[x]=tp;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=hed[x];i;i=nxt[i]) if(!top[tal[i]]) dfs2(tal[i],tal[i]);
}
int anc(int u,int k)
{
int v=u;
while(v&&dep[u]-dep[top[v]]<k) v=fa[top[v]];
if(!v) return 0;
return li[dfn[top[v]]+dep[u]-k-dep[top[v]]];
}
struct sgt
{
#define mid (lb+rb>>1)
int d[N<<2],ls[N<<2],rs[N<<2],idx;
int st[N<<2],tp;
void modify(int &x,int t,int lb,int rb)
{
if(!x) x=tp?st[tp--]:++idx;
d[x]++;
if(lb==rb) return;
if(t<=mid) modify(ls[x],t,lb,mid);
else modify(rs[x],t,mid+1,rb);
}
int query(int x,int t,int lb,int rb)
{
if(!x) return 0;
if(lb==rb) return d[x];
if(t<=mid) return query(ls[x],t,lb,mid);
return query(rs[x],t,mid+1,rb);
}
int merge(int x,int y,int lb,int rb)
{
if(!x||!y) return x|y;
d[x]+=d[y];
if(lb<rb)
ls[x]=merge(ls[x],ls[y],lb,mid),
rs[x]=merge(rs[x],rs[y],mid+1,rb);
d[y]=ls[y]=rs[y]=0,st[++tp]=y;
return x;
}
#undef mid
} tr;
void dfs3(int x)
{
(rt[x],dep[x],1,md);
for(int i=hed[x];i;i=nxt[i]) if(tal[i]^fa[x])
dfs3(tal[i]),rt[x]=(rt[x],rt[tal[i]],1,md);
for(int i=qh[x];i;i=qnxt[i])
ans[i]=(rt[x],dep[x]+ak[i],1,md)-1;
}
main()
{
scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]),adde(fa[i],i);
dfs1(1),dfs2(1,1);
for(int i=1;i<=q;i++)
{
int u,k;
scanf("%d%d",&u,&k);
av[i]=anc(u,k),ak[i]=k,addq(i);
}
dfs3(1);
for(int i=1;i<=q;i++) printf("%d ",ans[i]);
}