一种新的做法（感觉与题解区有重复）

前言：不会动态dp之类的东西qwq，只想知道有没有写题解的价值，应该不算tlqtj吧，如违规紫衫。
独立想出来的，感觉和题解的倍增和LCT做法很像。
方法是直接树链剖分+线段树，状态与LCT做法的那篇题解一样，即记

f_{l,r}

表示最左边选的点到左端点距离为

l

，最右边选的点到右端点距离为

r

（一共3*3个状态），处理区间合并时

k=3

时跳到一个点的儿子处理由于大部分题解都没怎么说明我不清楚其他题解的思路是否与我一致，即初始化

f_{1,1}

为该点周围所有点价值的最小值，如此设定即不需要转移时进行更多的分类讨论。
空间复杂度

O(n)

时间复杂度

O(n+q \log^2 n)

（

k

当作常数处理），若将

k

算上的话大概应该是

k^3

k^4

的级别。虽然复杂度较高，但可能是树剖常数小的原因，七百多毫秒足以跑完。理论上可以用猫树或者什么其他的东西优化到

O((n+q) \log n)

，但空间也需开到

O(n \log n)

。
AC代码如下（写得较丑，常数可能较大）：

CPP

#include<bits/stdc++.h>
#define scanf __builtin_scanf
#define printf __builtin_printf
#define puts __builtin_puts
#define px first
#define py second
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int N=200005;
const ll INF=1e18;
int n,q,k;
ll w[N],w_min[N];
vector<int> a[N];
struct val{
	ll v[3][3];//两边分别向中间蔓延的空格数
	int len;
	val(): len(0){memset(v,0,sizeof v);}
	val(const val& x){
		len=x.len;
		memcpy(v,x.v,sizeof v);
	}
	void reverse(){
		for(int i=1;i<3;i++)
			for(int j=0;j<i;j++)
				swap(v[i][j],v[j][i]);
	}
	friend val operator+(const val& x,const val& y){
		if(!x.len) return y;
		if(!y.len) return x;
		val ans;
		ans.len=x.len+y.len;
		#define ans_set(k,l) ans.v[i][j]=min(ans.v[i][j],x.v[i][k]+y.v[l][j])
		for(int i=0;i<k;++i)
			for(int j=0;j<k;++j){
				ans.v[i][j]=min(INF,x.v[i][0]+y.v[0][j]);
				if(j>=y.len) ans.v[i][j]=min(ans.v[i][j],x.v[i][j-y.len]);
				if(i>=x.len) ans.v[i][j]=min(ans.v[i][j],y.v[i-x.len][j]);
				if(k==2) ans_set(0,1),ans_set(1,0);
				if(k==3) ans_set(0,1),ans_set(0,2),ans_set(1,0),ans_set(1,1),ans_set(2,0);
			}
		return ans;
	}
};
int dfn[N],rnk[N],son[N],si[N],fa[N],top[N],clk,dep[N];
struct Node{
	int l,r;
	val w;
}tr[N<<2];
void build(const int& i,const int& l,const int& r){
	tr[i].l=l;
	tr[i].r=r;
	if(l==r){
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				tr[i].w.v[j][k]=INF;
		tr[i].w.v[0][0]=w[rnk[l]];
		tr[i].w.len=1;
		if(k==3) tr[i].w.v[1][1]=w_min[rnk[l]];
		return ;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tr[i].w=tr[i<<1].w+tr[i<<1|1].w;
}
val query(const int& i,const int& l,const int& r){
	if(tr[i].l>=l&&tr[i].r<=r) return tr[i].w;
	int mid=tr[i].l+tr[i].r>>1;
	if(l<=mid&&r>mid) return query(i<<1,l,r)+query(i<<1|1,l,r);
	if(l<=mid) return query(i<<1,l,r);
	if(r>mid) return query(i<<1|1,l,r);
}
void dfs1(const int& x){
	si[x]=1;
	for(int i:a[x]){
		if(i==fa[x]) continue;
		fa[i]=x;
		dep[i]=dep[x]+1;
		dfs1(i);
		si[x]+=si[i];
		if(si[i]>si[son[x]]) son[x]=i;
	}
}
void dfs2(const int& x,const int& tp){
	top[x]=tp;
	rnk[dfn[x]=++clk]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i:a[x]) if(i!=fa[x]&&i!=son[x]) dfs2(i,i);
}
ll tr_query(int x,int y){
	val ans1,ans2;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y),swap(ans1,ans2);
		ans1=query(1,dfn[top[x]],dfn[x])+ans1;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y),swap(ans1,ans2);
	ans1.reverse();
	return (ans1+query(1,dfn[x],dfn[y])+ans2).v[0][0];
}
signed main(){
	scanf("%d%d%d",&n,&q,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		w_min[i]=INF;
		for(int j:a[i]) w_min[i]=min(w_min[i],w[j]);
	}
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	for(int x,y;q--;) scanf("%d%d",&x,&y),printf("%lld\n",tr_query(x,y));
	return 0;
}

一种新的做法（感觉与题解区有重复）

讨论操作

回复

相关推荐

一种新的做法（感觉与题解区有重复）