[数据结构与算法][CF1336F]Journey

Journey

题解

又是一道阴间大码量题，话说这跟LCT完全无关的题为什么拉到LCT的版块里呀。

首先，我们发现这道题其实我们可以分两种情况讨论，一种是$lca$相同的链，一种是$lca$不同的链。
由于这两种情况各自对应的链覆盖不同处比较大，所以还是分开写比较好。

我们先关注$lca$不同的情况，显然，应该是长这个样子的。
懒得画了，直接放官解的图。

显然，存在一个$lca$较高的链与$lca$较低的链，假设它们分别为图中的$A,B$。
那么对于这个较低的链$B$，由于$A,B$呈现祖先关系，所以$A$至少需要覆盖$B$往下的一条长度为$K$的链。
即需要覆盖到图中的点$C$或者点$D$。
我们可以将它转化为$A$有一个端点在$C$或者$D$的子树中，如果是子树内的话，显然就可以映射到其$dfs$序在某个区间中。
$dfs$序这就好维护，我们可以考虑使用线段树维护。
我们在条链的$lca$上处理这条链，这条链上就相当于给从$lca$向两端走$K$步到的两个子树区间内$+1$，每个点上维护的就是该点处在多少个区间。
那我们每次查询就只需要询问链的两个端点在多少个区间，显然，这两个端点是不会有重复的区间的，毕竟这些链都只在该$lca$的一个子树内，我们这里只处理$lca$不同的链。
至于每次上传，就直接线段树合并就行了。
这不是时间复杂度是$O\left((n+m)\log n\right)$的。

至于$lca$相同的部分，它大概有这两种情况。


事实上，这两种都是十分类似的，我们可以用同一个方式处理。许多题解都提及用不同的方式处理，事实上是完全没必要的。
我们发现，对于两条$lca$相同的链$(A,B)$，$(C,D)$，我们可以尝试将其中两条链的端点任意组合，我们显然有$4$种方案，假设我们现在组合了$A,C$，那我们就去计算$lca(A,C)?>lca(B,D)$的长度。
我们发现，无论怎么组合，我们都会存在且进存在两种方案，它们的路径长度为原长，另外两种方案它们的长度为$0$，分别是原链与就一个$lca(A,B,C,D)$。
那么我们可以考虑将l每条链分成$A?>B$与$B?>A$两条放进去，与其它的链匹配，最后再将答案除以二。
对于两条链的匹配，就是对于$(X,Y)$与$(Z,W)$求出$lca(X,Z)?>lca(Y,W)$的长度，去看它合不合法。
显然，这也是比较好维护的，我们可以考虑树上启发式合并。
由于我们要求的是$lca(X,Z)?>lca(Y,W)$的长度不小于$K$，那么我们可以在$lca(X,Z)$处，观察$lca(Y,W)$是不是应该在距离$lca(X,Z)$距离$K$的地方。
转化一下，询问我们的链$(X,Y)$上，距离$lca(X,Z)$距离为$K$的点的子树内是否包含$W$。
那么我们相当于在树上启发式合并$(X,Y)$的时候，直接询问距离当前的$K$的点内部有多少个我们合并目标集合中的端点，这不是也可以用线段树合并嘛。
与上面一个不同的是，上面的是区间加单点查询，这是单点加区间查询。
只不过要启发式合并，所以对于一个$lca$是$O\left(n{\log }^{2}n\right)$的。

但如果我们每个点都要这样做一遍的话显然是不行的，但我们实际上要用的点并没有这么多，只有需要进行启发式合并的点是有用的。
那么我们可以对这个点上所有有用的操作建出一棵虚树，在虚树上进行处理。
由于虚树的大小是$O\left(操作个数\right)$的，所以这样的话我们这部分的时间复杂度就降到了$O\left(m{\log }^{2}m\right)$。

总时间复杂度$O\left(n\log n+m{\log }^{2}m\right)$。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 150005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double Ld;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int mod=1e5+7;
const int inv2=499122177;
const double jzm=0.999;
const int zero=2000;
const int n1=150;
const int orG=3,ivG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-8;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,m,K,head[MAXN],tot,dep[MAXN],f[MAXN][20];
int dfn[MAXN],rd[MAXN],idx,root[MAXN];LL ans;
int sta[MAXN<<1],stak,pre[MAXN],st[MAXN<<1],stk,id[MAXN];
vector<int>vec[MAXN],tmp[MAXN],G[MAXN];
struct ming{
	int lson,rson,sum;
	ming(){lson=rson=sum=0;}
};
struct ask{int u,v,w,id;}s[MAXN];
struct edge{int to,nxt;}e[MAXN<<1];
void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
class SegmentTree{
	private:
		ming tr[MAXN*50];int tot;
	public:
		void insert(int &rt,int l,int r,int al,int ar){
			if(l>r||l>ar||r<al||al>ar)return ;
			if(!rt)rt=++tot;int mid=l+r>>1;
			if(al<=l&&r<=ar){tr[rt].sum++;return ;}
			if(al<=mid)insert(tr[rt].lson,l,mid,al,ar);
			if(ar>mid)insert(tr[rt].rson,mid+1,r,al,ar);
		}
		int query(int rt,int l,int r,int ai){
			if(l>r||l>ai||r<ai||!rt)return 0;
			if(l==r)return tr[rt].sum;
			int mid=l+r>>1,res=tr[rt].sum;
			if(ai<=mid)res+=query(tr[rt].lson,l,mid,ai);
			if(ai>mid)res+=query(tr[rt].rson,mid+1,r,ai);
			return res;
		}
		void modify(int &rt,int l,int r,int ai){
			if(l>r||l>ai||r<ai)return ;
			if(!rt)rt=++tot;tr[rt].sum++;
			if(l==r)return ;int mid=l+r>>1;
			if(ai<=mid)modify(tr[rt].lson,l,mid,ai);
			if(ai>mid)modify(tr[rt].rson,mid+1,r,ai);
		}
		int askSum(int rt,int l,int r,int al,int ar){
			if(l>r||l>ar||r<al||al>ar||!rt)return 0;
			if(al<=l&&r<=ar)return tr[rt].sum;
			int mid=l+r>>1,res=0;
			if(al<=mid)res+=askSum(tr[rt].lson,l,mid,al,ar);
			if(ar>mid)res+=askSum(tr[rt].rson,mid+1,r,al,ar);
			return res;
		}
		int merge(int x,int y,int l,int r){
			if(!x||!y)return x+y;tr[x].sum+=tr[y].sum;
			if(l==r)return x;int mid=l+r>>1;
			tr[x].lson=merge(tr[x].lson,tr[y].lson,l,mid);
			tr[x].rson=merge(tr[x].rson,tr[y].rson,mid+1,r);
			return x;
		}
		void clear(){for(int i=1;i<=tot;i++)tr[i]=ming();tot=0;}
}T;
int lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int i=18;i>=0;i--)if(dep[f[b][i]]>=dep[a])b=f[b][i];
	if(a==b)return a;
	for(int i=18;i>=0;i--)if(f[a][i]^f[b][i])a=f[a][i],b=f[b][i];
	return f[a][0];
}
int findFa(int x,int dp){for(int i=18;i>=0;i--)if((dp&(1<<i)))x=f[x][i];return x;}
void dosaka1(int u,int fa){
	dep[u]=dep[fa]+1;dfn[u]=++idx;f[u][0]=fa;
	for(int i=1;i<19;i++)f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].nxt)
		if(e[i].to^fa)dosaka1(e[i].to,u);
	rd[u]=idx;
}
void dosaka2(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa)continue;
		dosaka2(v,u);root[u]=T.merge(root[u],root[v],1,n);
	}
	int siz=vec[u].size();
	for(int i=0;i<siz;i++){
		int x=vec[u][i],su=s[x].u,sv=s[x].v;
		ans+=T.query(root[u],1,n,dfn[su]);
		ans+=T.query(root[u],1,n,dfn[sv]);
	}
	for(int i=0;i<siz;i++){
		int x=vec[u][i],su=s[x].u,sv=s[x].v,w=s[x].w;
		if(dep[su]-dep[w]>=K)
			su=findFa(su,dep[su]-dep[w]-K),
			T.insert(root[u],1,n,dfn[su],rd[su]);
		if(dep[sv]-dep[w]>=K)
			sv=findFa(sv,dep[sv]-dep[w]-K),
			T.insert(root[u],1,n,dfn[sv],rd[sv]);
	}
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
signed main(){
	read(n);read(m);read(K);
	for(int i=1;i<n;i++){
		int u,v;read(u);read(v);
		addEdge(u,v);addEdge(v,u);
	}
	dosaka1(1,0);
	for(int i=1;i<=n;i++)id[i]=i;
	for(int i=1;i<=m;i++)
		read(s[i].u),read(s[i].v),s[i].id=i,
		vec[s[i].w=lca(s[i].u,s[i].v)].pb(i);
	dosaka2(1,0);T.clear();
	for(int i=1;i<=n;i++)root[i]=0;
	for(int i=1;i<=n;i++){
		int siz=vec[i].size();LL summ=0;stak=0;
		for(int j=0;j<siz;j++){
			int u=s[vec[i][j]].u,v=s[vec[i][j]].v;
			sta[++stak]=u;sta[++stak]=v;
		}
		sort(sta+1,sta+stak+1,cmp);
		stak=unique(sta+1,sta+stak+1)-sta-1;int lsk=stak; 
		for(int j=1;j<lsk;j++)sta[++stak]=lca(sta[j],sta[j+1]);
		sort(sta+1,sta+stak+1,cmp);
		stak=unique(sta+1,sta+stak+1)-sta-1;
		for(int j=1;j<=stak;j++)pre[sta[j]]=j,id[j]=j;stk=0;
		for(int j=0;j<siz;j++){
			int u=s[vec[i][j]].u,v=s[vec[i][j]].v;
			if(dep[u]+dep[v]-2*dep[s[vec[i][j]].w]<K)continue;
			tmp[pre[u]].pb(v);tmp[pre[v]].pb(u); 
		}
		for(int j=1;j<=stak;j++){
			while(stk&&rd[st[stk]]<dfn[sta[j]])stk--;
			if(stk)G[pre[st[stk]]].pb(j);st[++stk]=sta[j];
		}
		int L=dfn[i],R=rd[i];
		for(int j=stak;j>0;j--){
			int u=sta[j],siz=tmp[id[j]].size();
			for(int k=0,y;k<siz;k++){
				int v=tmp[id[j]][k];
				if(dep[u]-dep[i]>=K)summ+=T.askSum(root[u],L,R,L,R);
				else y=findFa(v,dep[v]+dep[u]-2*dep[i]-K),
					summ+=T.askSum(root[u],L,R,dfn[y],rd[y]);
				T.modify(root[u],L,R,dfn[v]);
			}
			siz=G[j].size();
			for(int k=0;k<siz;k++){
				int v=sta[G[j][k]],siz1=tmp[id[j]].size(),siz2=tmp[id[pre[v]]].size();
				int iu=id[pre[u]],iv=id[pre[v]];
				if(siz1>siz2)for(int l=0;l<siz2;l++){
					int x=tmp[iv][l],y;tmp[iu].pb(x);
					if(dep[u]-dep[i]>=K)summ+=T.askSum(root[u],L,R,L,R);
					else y=findFa(x,dep[x]+dep[u]-2*dep[i]-K),
						summ+=T.askSum(root[u],L,R,dfn[y],rd[y]);
				}
				else for(int l=0;l<siz1;l++){
					int x=tmp[iu][l],y;tmp[iv].pb(x);
					if(dep[u]-dep[i]>=K)summ+=T.askSum(root[v],L,R,L,R);
					else y=findFa(x,dep[x]+dep[u]-2*dep[i]-K),
						summ+=T.askSum(root[v],L,R,dfn[y],rd[y]);
				}
				if(siz1<=siz2)id[pre[u]]=id[pre[v]];
				root[u]=T.merge(root[u],root[v],L,R);
			}
		}
		ans+=summ/2LL; 
		for(int k=1;k<=stak;k++)tmp[k].clear(),G[k].clear();
		T.clear();for(int k=1;k<=stak;k++)root[sta[k]]=0;
	}
	printf("%lld\n",ans);
	return 0;
}

谢谢！！！