义乌中学暑假集训 2021.07.09 D

(Updated: )
oi

Description

给定一棵 $n$​ 个节点的树 $T$​，有 $m$​ 个询问，每次询问给定 $l,r$​，问存在多少个 $k\in Z$​，使从树上编号为 $l$​ 的点沿着 $l\rightarrow r$​ 的简单路径走 $k$​ 步恰好到达 $k$​。

$1\leq n\leq 3\times 10^5,1\leq m\leq 3\times 10^5$。

Solution

考虑树上从 $l$​ 走到 $r$​ 的路径可以拆成两段：$l\rightarrow lca,lca\rightarrow r$​。

令当前节点为 $k$，则可以分类讨论：

  • $l\rightarrow lca$​，显然此时步数为 $dep_l-dep_k$，那么由题意可得 $dep_l-dep_k=k$，移项，$dep_l=k+dep_k$，因此只需要预处理出 $k+dep_k$，然后每次询问利用树链剖分直接主席树上查询即可。
  • $lca\rightarrow r$，显然此时步数为 $dep_k-dep_{lca}+dep_l-dep_{lca}$，那么由题意可得 $dep_k+dep_l-2\times dep_{lca}=k$，移项，$dep_l-2\times dep_{lca}=k-dep_k$，与上一类同理处理即可。

最后注意下 $lca$ 可能算两次的情况。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
using namespace std;
Cn int N=3e5+10,M=11;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(RI x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
int n,m,fir[N],nxt[N<<1],son[N<<1],tot,dep[N],f[N],sz[N],mx[N],top[N],dfn[N],cnt,rtA[N<<1],rtB[N<<1],A[N<<1],B[N<<1],CA,CB;
struct Que{int l,r;}q[N];
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
I void Dfs1(CI x,CI fa){
    RI i;for(dep[x]=dep[f[x]=fa]+(sz[x]=1),i=fir[x];i;i=nxt[i]) to^fa&&(Dfs1(to,x),sz[x]+=sz[to],sz[to]>sz[mx[x]]&&(mx[x]=to));
}
I void Dfs2(CI x,CI Top){
    if(top[x]=Top,dfn[x]=++cnt,mx[x]) Dfs2(mx[x],Top);
    RI i;for(i=fir[x];i;i=nxt[i]) to^mx[x]&&to^f[x]&&(Dfs2(to,to),0);
}
I int LCA(RI x,RI y){
    W(top[x]^top[y]) dep[top[x]]<dep[top[y]]&&(swap(x,y),0),x=f[top[x]];
    return dep[x]<dep[y]?x:y;
}
class ChairmanTree{
    private:
        int id;struct node{int l,r,v;}T[N*40];
        #define mid (l+r>>1)
        #define LT T[x].l,l,mid
        #define RT T[x].r,mid+1,r
    public:
        I void U(CI p,RI pre,int& x,CI l=1,CI r=n){
            if(T[x=++id]=T[pre],T[x].v++,l==r) return ;
            p<=mid?U(p,T[pre].l,LT):U(p,T[pre].r,RT);
        }
        I int Q(CI L,CI R,CI x,CI l=1,CI r=n){
            if(L<=l&&r<=R) return T[x].v;
            RI S=0;return L<=mid&&(S+=Q(L,R,LT)),R>mid&&(S+=Q(L,R,RT)),S;
        }
}TA,TB;
I int QA(RI x,RI y,CI v){
    RI S=0;W(top[x]^top[y]) S+=TA.Q(dfn[top[x]],dfn[x],rtA[v]),x=f[top[x]];
    return S+TA.Q(dfn[y],dfn[x],rtA[v]);
}
I int QB(RI x,RI y,CI v){
    RI S=0;W(top[x]^top[y]) S+=TB.Q(dfn[top[x]],dfn[x],rtB[v]),x=f[top[x]];
    return S+TB.Q(dfn[y]+1,dfn[x],rtB[v]);
}
#define LWA(x) (lower_bound(A+1,A+CA+1,x)-A)
#define LWB(x) (lower_bound(B+1,B+CB+1,x)-B)
int main(){
    RI i,x,y,t;for(read(n),read(m),i=1;i<n;i++) read(x),read(y),Add(x,y),Add(y,x);
    for(Dfs1(1,0),Dfs2(1,1),i=1;i<=m;i++) read(q[i].l),read(q[i].r),t=LCA(q[i].l,q[i].r),A[++CA]=dep[q[i].l],B[++CB]=dep[t]*2-dep[q[i].l];
    for(i=1;i<=n;i++) A[++CA]=i+dep[i],B[++CB]=dep[i]-i;sort(A+1,A+CA+1),CA=unique(A+1,A+CA+1)-A-1,sort(B+1,B+CB+1),CB=unique(B+1,B+CB+1)-B-1;
    for(i=1;i<=n;i++) TA.U(dfn[i],rtA[LWA(i+dep[i])],rtA[LWA(i+dep[i])]),TB.U(dfn[i],rtB[LWB(dep[i]-i)],rtB[LWB(dep[i]-i)]);
    for(i=1;i<=m;i++) t=LCA(q[i].l,q[i].r),write(QA(q[i].l,t,LWA(dep[q[i].l]))+QB(q[i].r,t,LWB(dep[t]*2-dep[q[i].l]))),pc('\n');return 0;
}