先来一道简化版：

关联点 2

• 给出一棵二叉树，每个点有点权 ??

• 如果 ? 在 ? 的左（右）子树中，且 ? 到 ? 的距离为 ??，则称 ?

为 ? 的左（右）关联点

• 求每个点的左、右关联点个数

• ? ≤ 10^6

 

子树内距离根为x深度的点有多少个

不能爆搜。

但是，可以利用dfs的性质，便利完a的子树，才会出来。

所以，可以用一个全局数组记录dep[i]表示深度为i的点出现了几次

进入x，记录dep[dep[x]+va]个数=old，然后把dep[dep[x]]++

回溯的时候，把new-old即可求出答案。

 

 

进入正题：

 

对于树上路径问题。几个处理思路如下：

1.树链剖分：然鹅每个点都有询问，，不会维护

2.点分治：和S,T,LCA都有关系。不能直接分割。

3.树上差分。也许可以试试。

 

还有几种处理思路：

1.枚举所有的人，在路径上留下标记。但是路径还是过长啊。不能直接走。

2.考虑一个人被一个点发现的条件。

可以对于s，t列出两个满足的式子。

然后，全局变量两个桶维护值。

dfs一遍树。

进入的时候，把两个要统计的位置初值记下来。

子树回溯完了之后，两个位置的差值就是子树中可以被观察到的S,T的个数。

但是，S，T不能只出现不删除。因为可能在x子树里出现，然后不经过x。。。

所以，在LCA的fa标记减去S，LCA标记减去T

到了这个点就减去桶中的位置的贡献。

这样，所有经过j点的被观察到的情况都考虑到了。

 

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;const int N=300000+4;int n,m;struct node{    int nxt,to;    int id;}e[2*N],bian[2*N];int cnt1,cnt2;int ff[N];int hd[N],pre[N];il void rd(int &x){    char ch;x=0;    while(!isdigit(ch=getchar()));    for(x=numb;isdigit(ch=getchar());x=(x<<1)+(x<<3)+numb);}il void prin(int x){    if(x/10) prin(x/10);    putchar(x%10+'0');}il void add(int x,int y){    e[++cnt1].nxt=hd[x];    e[cnt1].to=y;    hd[x]=cnt1;}il void upda(int x,int y,int z){    bian[++cnt2].nxt=pre[x];    bian[cnt2].to=y;    bian[cnt2].id=z;    pre[x]=cnt2;}int lca[N],S[N],T[N];int fa[N];int dep[N];int w[N];int ans[N];il int fin(int x){    return fa[x]==x?x:fa[x]=fin(fa[x]);}bool vis[N];il void tarjan(int x,int d){    dep[x]=d;    fa[x]=x;    vis[x]=1;    for(reg i=pre[x];i;i=bian[i].nxt){        int y=bian[i].to;        if(vis[y]){            lca[bian[i].id]=fin(y);        }    }    for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(!vis[y]){            ff[y]=x;            tarjan(y,d+1);            fa[y]=x;        }    }}int up[2*N],down[2*N];vector
      
       
         >mup[N];vector
        
         
           >mdo[N];il void dfs(int x){    int tagup=up[dep[x]+w[x]];    int tagdown=down[dep[x]-w[x]+n];    for(int i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(y==ff[x]) continue;        dfs(y);    }    for(reg i=0;i
         
        
       
      
     

 

 

总结：

1.入手点：不考虑人在路上留下标记，而考虑一个人被一个点观察到的条件是什么。

2.开一个全局变量，进入x记录一次，离开x记录一次，这样就能统计x子树中某个信息出现的次数了。

只需要O(1)

（当然，你要是动态开点线段树+最后合并也可以23333）