树上询问
你有一棵 \(n\) 个节点的树 \(T\) ，回答 \(m\) 个询问，每次询问给你两个整数 \(l,r\) ，问存在多少个整数 \(k\) 使得从 \(l\) 沿着 \(l->r\) 的简单路径走 \(k\) 步恰好到 \(k\) ，\(n,m\le 10^6\)。
解题思路
分析一下式子，可以发现，设 \(LCA(l,r)=z\) ，若 \(k\) 在 \(l->z\) 路径上，有 \(deep_l-deep_k=k\) ，即为 \(deep_l=deep_k+k\) ，即为统计 \(l->z\) 上有多少个节点 \(i\) 满足 \(deep_i+i=deep_l\) 。
而在 \(z->r\) 路径上时，有 \(deep_k-deep_z+deep_l-deep_z=k\) ，即为 \(deep_k-k=deep_z \times 2 -deep_l\) ，即为统计 \(r->z\) 上有多少个节点 \(i\) 满足 \(deep_i-i=deep_z \times 2 -deep_l\) 。
以第一种情况为例，将所有询问离线下来，然后从根节点开始遍历一遍树。
途径一个节点 \(i\) 时就把 \(i+deep_i\) 在一个数组中 \(v\) 存下来，每次处理询问时只需在 \(v\) 中找即可。
第二种情况同理，只是 \(deep_i-i\) 可能为负数，需要离散化或开 \(map\) 。
总时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
struct datay
{
int x,y,z;
}t[1200005];
int n,m,deep[300005],f[300005][21],v[600005];
map<int,int> v1;
vector<int> a[300005];
vector<datay> d[300005];
void dijah(int x,int y)
{
f[x][0]=y;
deep[x]=deep[y]+1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dijah(a[x][i],x);
}
return;
}
int LCA(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
for(int i=20;i>=0;i--)
{
if(deep[f[x][i]]>=deep[y])x=f[x][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
}
return f[x][0];
}
bool cmp1(datay q,datay w)
{
return q.z<w.z;
}
void gaia(int x,int y)
{
v[x+deep[x]]++;
v1[deep[x]-x]++;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
gaia(a[x][i],x);
}
for(int i=0;i<d[x].size();i++)
{
if(d[x][i].z%2==1)d[x][i].x=v[d[x][i].y];
else d[x][i].x=v1[d[x][i].y];
}
v[x+deep[x]]--;
v1[deep[x]-x]--;
return;
}
int main()
{
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
dijah(1,0);
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
z=LCA(x,y);
t[i*4-3].x=x;
t[i*4-3].y=deep[x];
t[i*4-3].z=i*4-3;
t[i*4-2].x=y;
t[i*4-2].y=deep[z]-(deep[x]-deep[z]);
t[i*4-2].z=i*4-2;
t[i*4-1].x=z;
t[i*4-1].y=deep[x];
t[i*4-1].z=i*4-1;
t[i*4].x=f[z][0];
t[i*4].y=deep[z]-(deep[x]-deep[z]);
t[i*4].z=i*4;
}
for(int i=1;i<=4*m;i++)d[t[i].x].push_back(t[i]);
gaia(1,0);
long long g=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<d[i].size();j++)t[++g]=d[i][j];
}
sort(t+1,t+g+1,cmp1);
for(int i=1;i<=m;i++)
{
printf("%d\n",t[i*4-3].x+t[i*4-2].x-t[i*4-1].x-t[i*4].x);
}
return 0;
}