1 条题解
-
1
vp 时写了 1.5h 才过的题，看来我还是太逊了。
来发树状数组题解。
洛谷中有一篇树状数组题解，可惜被我 hack 掉了。
先考虑满足第一棵树的性质，必然需要满足所选的点在一条链上。
然后贪心去取，如果当前选的点和之前的点矛盾，就把之前的去掉。
一个性质是每次最多去掉一个点，否则在加入这个点之前就矛盾了。
树状数组维护一下 dfs 序，判断是否矛盾。
注意判断矛盾既要判断自己是否在别的点的子树中，也需要判断别的是否在自己的子树中。
代码
#include<bits/stdc++.h> using namespace std; const int N=3e5+5; int in[N],out[N],c[2][N],fa[N],dep[N],n,ti; vector<int> e[N],tr[N]; void dfs1(int x){ in[x]=++ti; for(int y:tr[x])dfs1(y); out[x]=ti; } void dfs(int x){for(int y:e[x])dep[y]=dep[x]+1,dfs(y);} void add(int p,int x,int z){for(;x<=n;x+=x&-x)c[p][x]+=z;} int ask(int p,int x){if(!x)return 0;int ans=0;for(;x;x-=x&-x)ans+=c[p][x];return ans;} void add(int x){ add(0,in[x],x),add(0,out[x]+1,-x); add(1,in[x],x); } void del(int x){ add(0,in[x],-x),add(0,out[x]+1,x); add(1,in[x],-x); } int ans=0,sum=0; void dfs2(int x){ int t,ff=0; if(t=ask(0,in[x]))del(t),sum--,ff=t; if(t=ask(1,out[x])-ask(1,in[x]-1))del(t),sum--,ff=t; add(x),sum++; ans=max(ans,sum); for(int y:e[x])dfs2(y); del(x),sum--; if(ff)add(ff),sum++; } void work(){ ans=sum=0; scanf("%d",&n); for(int i=2;i<=n;i++)scanf("%d",&fa[i]),e[fa[i]].push_back(i); for(int i=2,x;i<=n;i++)scanf("%d",&x),tr[x].push_back(i); dfs1(1); dfs(1); dfs2(1); printf("%d\n",ans); for(int i=1;i<=n;i++)e[i].clear(),tr[i].clear(),dep[i]=0; ti=0; } int _; int main(){ scanf("%d",&_); while(_--)work(); }
- 1
