```cpp
if(siz[son[p]]<siz[v]){
v=son[p];
}
```
@[Bant_Metor](/user/389729) 瞪眼法瞪出来的。。。
by fjy666 @ 2023-11-23 19:18:09
@[fjy666](/user/366338)
谢谢！复杂度有优化！
（话说瞪眼看出来也太强了吧）
by Bant_Metor @ 2023-11-23 19:22:07
@[Bant_Metor](/user/389729) 给你的代码做了一些优化，把 cin 换成了 scanf，去掉了 #define int long long，变成了 75 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define debug cout<<-1<<endl
const int maxn=1e5+5;
int n,t;
vector<int>q[maxn];
int id[maxn];
int fa[maxn],top[maxn],son[maxn],siz[maxn],dep[maxn];
// string opt; // 0
int ans[4*maxn],num,tag[4*maxn];
int cnt=0;
int T;
void dfs1(int p){
siz[p]=1;
dep[p]=dep[fa[p]]+1;
for(int i=0;i<q[p].size();i++){
int v=q[p][i];
if(v!=fa[p]){
fa[v]=p;
dfs1(v);
siz[p]+=siz[v];
if(siz[son[p]]<siz[v]){
// v=son[p];
son[p] = v; // 1
}
}
}
}
void dfs2(int p,int tp){
top[p]=tp;
id[p]=++cnt;
if(son[p]){
dfs2(son[p],tp);
}
for(int i=0;i<q[p].size();i++){
int v=q[p][i];
if(v!=fa[p]&&v!=son[p]){
dfs2(v,v);
}
}
}
inline int ls(int a){
return 2*a;
}
inline int rs(int a){
return 2*a+1;
}
inline void pushup(int a){
ans[a]=ans[ls(a)]+ans[rs(a)];
}
void build(int l,int r,int p){
tag[p]=-1;
if(l==r){
ans[p]=1;//前查1 后查0
return;
}
int mid=(l+r)/2;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
pushup(p);
}
inline void f(int l,int r,int p,int k){
if(k==-1){
return;
}
else{
if(k==1){
ans[p]=0;
tag[p]=1;
}
else{
ans[p]=r-l+1;
tag[p]=0;
}
}
}
void pushdown(int l,int r,int p){
int mid=(l+r)/2;
f(l,mid,ls(p),tag[p]);
f(mid+1,r,rs(p),tag[p]);
tag[p]=-1;
}
int change(int nl,int nr,int l,int r,int p,int k){
if(nl<=l&&r<=nr){
int rett=ans[p];
f(l,r,p,k);
return rett;
}
int ret=0;
pushdown(l,r,p);
int mid=(l+r)/2;
if(mid>=nl){
ret+=change(nl,nr,l,mid,ls(p),k);
}
if(mid<nr){
ret+=change(nl,nr,mid+1,r,rs(p),k);
}
pushup(p);
return ret;
}
/*
int query(int nl,int nr,int l,int r,int p){
int ret=0;
//cout<<l<<" "<<r<<endl;
if(nl<=l&&r<=nr){
return ans[p];
}
pushdown(l,r,p);
int mid=(l+r)/2;
if(mid>=nl){
ret+=query(nl,nr,l,mid,ls(p));
}
if(mid<nr){
ret+=query(nl,nr,mid+1,r,rs(p));
}
return ret;//此现改为 0 的个数
}
*/
int update(int x,int y,int k){
int ret=0;
while(top[x]!=top[y]){
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=change(id[top[x]],id[x],1,n,1,k);
x=fa[top[x]];
}
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=change(id[y],id[x],1,n,1,k);
return ret;
}
/*
int sum(int x,int y){
int ret=0;
while(top[x]!=top[y]){
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=query(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]<dep[y]){
swap(x,y);
}
return ret+query(id[y],id[x],1,n,1);
}
*/
signed main(){
// freopen("P2146_2.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<n;i++){
int vv=0;
scanf("%d",&vv);
q[i].push_back(vv);
q[vv].push_back(i);
}
dfs1(0);
dfs2(0,0);
build(1,n,1);
scanf("%d",&T);
//cout<<T<<endl;
while(T--){
int x=0;
char opt[5];
scanf("%s", opt); //改scanf
scanf("%d",&x);
if(opt[0]=='i'){//下载改链
//query(id[0],id[x],1,n,1)
printf("%d\n",update(0,x,1));
}//卸载删子树
else{
//num=query(id[x],id[x]+siz[x]-1,1,n,1);
//change(id[x],id[x]+siz[x]-1,1,n,1,0);
printf("%d\n",siz[x]-change(id[x],id[x]+siz[x]-1,1,n,1,0));
}
}
}
```
by fjy666 @ 2023-11-23 19:33:05
@[Bant_Metor](/user/389729)
```cpp
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define debug cout<<-1<<endl
const int maxn=1e5+5;
int n,t;
vector<int>q[maxn];
int id[maxn];
int fa[maxn],top[maxn],son[maxn],siz[maxn],dep[maxn];
// string opt; // 0
int ans[4*maxn],tag[4*maxn],num;
int cnt=0;
int T;
void dfs1(int p){
siz[p]=1;
dep[p]=dep[fa[p]]+1;
for(int i=0;i<q[p].size();i++){
int v=q[p][i];
if(v!=fa[p]){
fa[v]=p;
dfs1(v);
siz[p]+=siz[v];
if(siz[son[p]]<siz[v] || son[p] == 0){
// v=son[p];
son[p] = v; // 1
}
}
}
}
void dfs2(int p,int tp){
top[p]=tp;
id[p]=++cnt;
if(son[p]){
dfs2(son[p],tp);
}
for(int i=0;i<q[p].size();i++){
int v=q[p][i];
if(v!=fa[p]&&v!=son[p]){
dfs2(v,v);
}
}
}
#define ls(a) (a<<1)
#define rs(a) (a<<1|1)
// inline int ls(int a){
// return 2*a;
// }
// inline int rs(int a){
// return 2*a+1;
// }
inline void pushup(int a){
ans[a]=ans[ls(a)]+ans[rs(a)];
}
void build(int l,int r,int p){
tag[p]=-1;
if(l==r){
ans[p]=1;//前查1 后查0
return;
}
int mid=(l+r)/2;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
pushup(p);
}
inline void f(int l,int r,int p,int k){
if(k==-1){
return;
}
// else{
if(k==1){
ans[p]=0;
tag[p]=1;
}
else{
ans[p]=r-l+1;
tag[p]=0;
}
// }
}
inline void pushdown(int l,int r,int p){
int mid=(l+r)/2;
f(l,mid,ls(p),tag[p]);
f(mid+1,r,rs(p),tag[p]);
tag[p]=-1;
}
int change(int nl,int nr,int l,int r,int p,int k){
if(nl<=l&&r<=nr){
int rett=ans[p];
f(l,r,p,k);
return rett;
}
int ret=0;
pushdown(l,r,p);
int mid=(l+r)/2;
if(mid>=nl){
ret+=change(nl,nr,l,mid,ls(p),k);
}
if(mid<nr){
ret+=change(nl,nr,mid+1,r,rs(p),k);
}
pushup(p);
return ret;
}
/*
int query(int nl,int nr,int l,int r,int p){
int ret=0;
//cout<<l<<" "<<r<<endl;
if(nl<=l&&r<=nr){
return ans[p];
}
pushdown(l,r,p);
int mid=(l+r)/2;
if(mid>=nl){
ret+=query(nl,nr,l,mid,ls(p));
}
if(mid<nr){
ret+=query(nl,nr,mid+1,r,rs(p));
}
return ret;//此现改为 0 的个数
}
*/
int update(int x,int y,int k){
int ret=0;
while(top[x]!=top[y]){
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=change(id[top[x]],id[x],1,n,1,k);
x=fa[top[x]];
}
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=change(id[y],id[x],1,n,1,k);
return ret;
}
/*
int sum(int x,int y){
int ret=0;
while(top[x]!=top[y]){
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=query(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]<dep[y]){
swap(x,y);
}
return ret+query(id[y],id[x],1,n,1);
}
*/
int main(){
// freopen("P2146_2.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<n;i++){
int vv=0;
scanf("%d",&vv);
q[i].push_back(vv);
q[vv].push_back(i);
}
dfs1(0);
dfs2(0,0);
build(1,n,1);
scanf("%d",&T);
//cout<<T<<endl;
while(T--){
int x=0;
char opt[5];
scanf("%s", opt); //改scanf
scanf("%d",&x);
if(opt[0]=='i'){//下载改链
//query(id[0],id[x],1,n,1)
printf("%d\n",update(0,x,1));
}//卸载删子树
else{
//num=query(id[x],id[x]+siz[x]-1,1,n,1);
//change(id[x],id[x]+siz[x]-1,1,n,1,0);
printf("%d\n",siz[x]-change(id[x],id[x]+siz[x]-1,1,n,1,0));
}
}
}
```
过了。具体来说，由于这道题节点从 $0$ 开始，需要特判 son = 0 的情况。希望对你有帮助。
by fjy666 @ 2023-11-23 19:36:08
@[fjy666](/user/366338)
非常感谢您，我确实这次从中学到了很多
by Bant_Metor @ 2023-11-23 19:37:43