当复习了一下树链剖分，WA了一片，调了半天，发现是把修改操作写错了。反正以后记住这里和倍增求lca类似，都是依靠点的深度来决定哪个点往上跳。
也学习了一下树上差分的方法来做这道题，当然要比树链剖分简单不少，以后记住树上差分的核心操作就是
f[u]++, f[v]++, f[lca(u,v)]--,f[fa(lca(u,v))]--
然后每个节点 dfs 中累加子节点的 f 值就好了。
上代码
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 300010 using namespace std; typedef long long LL; int n,a[MAXN]; int head[MAXN],to[MAXN*2],nxt[MAXN*2],tot=1; int siz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN],id[MAXN],idn; void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;} void dfs1(int u,int rt,int deep){ siz[u]=1;fa[u]=rt;dep[u]=deep; for(int i=head[u];i;i=nxt[i]){ if(to[i]==rt) continue; dfs1(to[i],u,deep+1); siz[u]+=siz[to[i]]; if(siz[to[i]]>siz[son[u]]) son[u]=to[i]; } } void dfs2(int u,int tp){ top[u]=tp;id[u]=++idn; if(!son[u]) return; dfs2(son[u],tp); for(int i=head[u];i;i=nxt[i]){ if(to[i]==son[u]||to[i]==fa[u]) continue; dfs2(to[i],to[i]); } } struct SegmentTree{ #define mid ((l+r)>>1) int sum[MAXN*4],tag[MAXN*4]; void build(){memset(sum,0,sizeof(sum));memset(tag,0,sizeof(tag));} void pushdown(int id,int l,int r){ int llen=mid-l+1,rlen=r-mid; sum[id<<1]+=tag[id]*llen;tag[id<<1]+=tag[id]; sum[id<<1|1]+=tag[id]*rlen;tag[id<<1|1]+=tag[id]; tag[id]=0; } void update(int id,int l,int r,int L,int R,int x){ if(L<=l&&r<=R){sum[id]+=x*(r-l+1);tag[id]+=x;return;} if(tag[id]) pushdown(id,l,r); if(L<=mid) update(id<<1,l,mid,L,R,x); if(R>mid) update(id<<1|1,mid+1,r,L,R,x); sum[id]=sum[id<<1]+sum[id<<1|1]; } int ask(int id,int l,int r,int pos){ if(l==pos&&pos==r) return sum[id]; if(tag[id]) pushdown(id,l,r); if(pos<=mid) return ask(id<<1,l,mid,pos); else return ask(id<<1|1,mid+1,r,pos); } }tree; void preUpdate(int x,int y,int z){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); tree.update(1,1,n,id[top[x]],id[x],z); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); tree.update(1,1,n,id[x],id[y],z); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v);add(u,v);add(v,u);} dfs1(1,0,1); dfs2(1,1); tree.build(); for(int i=1;i<n;i++) { preUpdate(a[i],a[i+1],1); preUpdate(a[i+1],a[i+1],-1); } for(int i=1;i<=n;i++) printf("%d ",tree.ask(1,1,n,id[i])); return 0; }
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 300010 using namespace std; int n,a[MAXN],ans[MAXN],dep[MAXN]; int head[MAXN],to[MAXN*2],nxt[MAXN*2],tot=1; int fa[MAXN][22]; void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;} int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f; } void dfs1(int u,int rt,int deep){ fa[u][0]=rt;dep[u]=deep; for(int i=head[u];i;i=nxt[i]){ if(to[i]==rt) continue; dfs1(to[i],u,deep+1); } } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void dfs2(int u){ for(int i=head[u];i;i=nxt[i]){ if(to[i]==fa[u][0]) continue; dfs2(to[i]); ans[u]+=ans[to[i]]; } } int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1,u,v;i<n;i++){u=read();v=read();add(u,v);add(v,u);} dfs1(1,0,1); for(int i=1;i<=20;i++) for(int u=1;u<=n;u++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=1;i<n;i++){ int root=lca(a[i],a[i+1]); ans[a[i]]++;ans[a[i+1]]++;ans[root]--;ans[fa[root][0]]--; } dfs2(1); for(int i=2;i<=n;i++) ans[a[i]]--; for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }