华中科技大学程序设计邀请赛网络赛 F War

题意

给出一个n个点的树，询问编号在一个区间内的点到给定点的最近距离。

题解

分块暴力求解，整块中用SPFA预处理，零散的用LCA求解。
首先根据内存限制，计算出打开能开 $200 * N$ 的数组，所以，每 $500$ 个点为一块，在块内跑一边SPFA，求出块内的点到其他点的最短路。
询问区间 $[l, r]$ ,分为多个整块的和多个零散的在块以外的，整块的就用之前SPFA处理的求解，零散的就分别于目标点做LCA，求最小值即可。

需要注意的是，因为要大量求解LCA，必须使用RMQ的方法，才能 $O (1)$ 求解。

代码

#include<bits/stdc++.h>
#define N 100510
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
typedef pair<int,int> pi;
typedef pair<int,pi> pp;
typedef __gnu_pbds::priority_queue<pp,greater<pp> > heap;
int n,m;
int L[N],st[N<<1],dp[22][N<<1],d[N],cnt;
vector<pi>a[N];
void lable(int x,int ffa,int p){
	st[x]=++cnt;
	dp[0][cnt]=x;
    for (auto i:a[x]) if (i.fi!=ffa){
        d[i.fi]=d[x]+i.se;
        L[i.fi]=p+1;
        lable(i.fi,x,p+1);
        dp[0][++cnt]=x;
    }
}
int lg[N<<1];
void preprocess(){
	for(int i=1;(1<<i)<=cnt;i++) lg[1<<i]=1;
	for(int i=1;i<=cnt;i++) lg[i]+=lg[i-1];
	for (int j=1;(1<<j)<=cnt;j++)
		for (int i=1;i<=cnt;i++){
			dp[j][i]=dp[j-1][i+(1<<j-1)];
			if (L[dp[j][i]]>L[dp[j-1][i]])
				dp[j][i]=dp[j-1][i];
		}
}

inline int query(int p,int q){
    p=st[p],q=st[q];
    if (p>q) swap(p,q);
    int t=lg[q-p];
    return L[dp[t][p]]<L[dp[t][q-(1<<t)+1]]?dp[t][p]:dp[t][q-(1<<t)+1];
}
inline int ask(int x,int y){
	int t=query(x,y);
	return d[x]+d[y]-d[t]*2;
}

int sz=500,id[205][N],q[N<<2];
void spfa(int x,int * d){
	bitset<N> bt(0); int h=0,t=0;
	for (int i=1;i<=n;i++) d[i]=1e9;
	for(int i=0;i<500;i++) 
		d[x+i]=0,q[++t]=x+i,bt[x+i]=1;
	
	while(h<=t){
		int x=q[++h];
		for (auto i:a[x]) if (d[i.fi]>d[x]+i.se){
			d[i.fi]=d[x]+i.se;
			if (bt[i.fi]==0)
				q[++t]=i.fi,bt[i.fi]=1;
		}
		bt[x]=0;
	}
}

int main()
{
	scc(n,m);
	for (int i=1,x,y,z;i<n;i++){
		sccc(x,y,z);
		a[x].pb(pi(y,z)),a[y].pb(pi(x,z));
	}
	lable(1,-1,0);
	preprocess();
	for (int i=0;i<=n;i+=sz) spfa(i,id[i/500]);
	while(m--){
		int x,y,z;
		sccc(x,y,z);
		int ans=1e9;
		int l=y/sz*sz,r=z/sz*sz;
		if (l<y) l+=sz;
		while(y<l && y<=z) ans=min(ans,ask(x,y++));

		while(z>=r && z>=y) ans=min(ans,ask(x,z--));
		
		while(l<r){
			ans=min(ans,id[l/500][x]);
			l+=sz;
		}
		printf("%d\n",ans);
	}
}

LCA的RMQ方法模板

void lable(int x,int ffa,int p)
{
	st[x]=++cnt;
	dp[0][cnt]=x;
    for (auto i:a[x]) if (i.fi!=ffa){
        d[i.fi]=d[x]+i.se;
        L[i.fi]=p+1;
        lable(i.fi,x,p+1);
        dp[0][++cnt]=x;
    }
}
void preprocess()
{
	for(int i=1;(1<<i)<=cnt;i++) lg[1<<i]=1;
	for(int i=1;i<=cnt;i++) lg[i]+=lg[i-1];
	for (int j=1;(1<<j)<=cnt;j++)
		for (int i=1;i<=cnt;i++){
			dp[j][i]=dp[j-1][i+(1<<j-1)];
			if (L[dp[j][i]]>L[dp[j-1][i]])
				dp[j][i]=dp[j-1][i];
		}
}

int query(int p,int q)
{
    p=st[p],q=st[q];
    if (p>q) swap(p,q);
    int t=lg[q-p];
    return L[dp[t][p]]<L[dp[t][q-(1<<t)+1]]?dp[t][p]:dp[t][q-(1<<t)+1];
}