@[Azure__](/user/565945) 2操作的第2行应该是
```cpp
updata(df[a[i]]+sz[a[i]]);
```
罢
by Skyjoy @ 2022-08-09 10:24:30
@[Skyjoy](/user/178556) 改完还是一样的,各个测试点都还是一样的
by Azure__ @ 2022-08-09 10:26:44
因为 $a_i$ 子树的范围是 $[dfn[a_i],dfn[a_i]+siz[a_i])$ ,所以在差分中修改的右端点应该是 $dfn[a_i]+siz[a_i]$ 。同时你可能会需要特判 $dfn[a_i]+siz[a_i]>n$ 的情况,但我没做过这道题所以不清楚
by Skyjoy @ 2022-08-09 10:27:05
不过确实是
```cpp
updata(df[a[i]]+sz[a[i]],1);
```
by Azure__ @ 2022-08-09 10:27:49
@[Skyjoy](/user/178556) 特判之后还是一样,有LOJ的测试信息,您要不要看看
by Azure__ @ 2022-08-09 10:29:51
@[Azure__](/user/565945) 可以,帮你调一下,我自己也做一遍(
by 天富星 @ 2022-08-09 10:31:38
@[天富星](/user/399997) [LOJ测试信息](https://loj.ac/s/1546503)
by Azure__ @ 2022-08-09 10:33:37
@[Azure__](/user/565945) 过了,代码如下
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char c; int x=0,f=1; c=getchar();
while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
return x*f;
}
int dep[200005],fa[200005][40],lg[200005],sz[200005],df[200005],n,m,tot;
//dep[i]:i号节点深度。 df[i]:i号节点的dfs序。 sz[i]:i号节点的孩子总数。
int c[200005],ans[200005],opt[200005],a[200005],b[200005];
// c:树状数组。 ans[i]:第i次操作产生的答案
vector<int> q[200005];// 记录询问的编号
vector<int> edge[200005];// 存边
inline void dfs(int k,int fath){
fa[k][0]=fath; dep[k]=dep[fath]+1;
if(k==0) dep[k]=0;
else df[k]=++tot;
sz[k]=1;
for(register int i=1;i<=lg[dep[k]];i++){
fa[k][i]=fa[fa[k][i-1]][i-1];
}
for(register int i=0;i<edge[k].size();i++){
if(edge[k][i]!=fath){
dfs(edge[k][i],k);
sz[k]+=sz[edge[k][i]];
}
}
}
inline int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]){
x=fa[x][lg[dep[x]-dep[y]]-1];
}
if(x==y) return x;
for(register int i=lg[dep[x]]-1;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i]; y=fa[y][i];
}
}
return fa[x][0];
}
inline int lowbit(int x){
return x&(-x);
}
inline void updata(int x,int u){
for(register int i=x;i<=n;i+=lowbit(i)){
c[i]+=u;
}
}
inline int sum(int x){
int ans=0;
for(register int i=x;i>0;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
inline int ask(int x,int y){
int lca=LCA(x,y);
return sum(df[x])+sum(df[y])-sum(df[lca])-sum(df[fa[lca][0]]);
}
int main()
{
n=read();
int root;
for(register int i=1;i<=n;i++){
int t=read();
if(t==0) root=i;
if(t!=0){
edge[t].push_back(i);
edge[i].push_back(t);
}
}
for(register int i=1;i<=n;i++){
lg[i]=lg[i>>1]+1;
}
dfs(root,0);
m=read();
for(register int i=1;i<=m;i++){
opt[i]=read();
if(opt[i]==1){
a[i]=read(); b[i]=read(); int t=read();
if(i-t>0)q[i-t].push_back(i);
}
if(opt[i]==2){
a[i]=read();
}
}
for(register int i=1;i<=m;i++){
for(register int j=0;j<q[i].size();j++){
ans[q[i][j]]=ask(a[q[i][j]],b[q[i][j]]);
}
if(opt[i]==1){
int d=dep[a[i]]+dep[b[i]]-2*dep[LCA(a[i],b[i])]+1;
printf("%d %d\n",d,ans[i]);
}
if(opt[i]==2){
updata(df[a[i]],1);
updata(df[a[i]]+sz[a[i]],-1);
}
}
return 0;
}
```
两个问题:
1.ask 函数中的 fa[lca][0] 外要套 dfs 序
2.将询问离线时要判断 i-t 会不会小于0
关注的话关注 Skyjoy 就行了,我是他小号 /cy
by 天富星 @ 2022-08-09 10:46:21
@[天富星](/user/399997) %%% 感谢dalao
by Azure__ @ 2022-08-09 10:47:37