专栏文章

题解：P14468 [COCI 2025/2026 #1] 和谐 / Harmonija

llight_searcher
P14468题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minbpcpb
此快照首次捕获于
2025/12/01 23:47
3 个月前
此快照最后确认于
2025/12/01 23:47
3 个月前
查看原文
怎么有这么典的题？
考虑 dp，设 fi,0f_{i,0} 表示前 ii 个红蓝数量相等的最大值，fi,1f_{i,1} 表示前 ii 个红比蓝多 11 个的答案，fi,2f_{i,2} 表示前 ii 个红比蓝多 22 个的答案，fi,3f_{i,3} 表示前 ii 个蓝比红多 11 个的答案，fi,4f_{i,4} 表示前 ii 个蓝比红多 22 个的答案，转移非常简单，这里不多赘述。
考虑把这个转移写成矩阵的形式：
[fi−1,0fi−1,1fi−1,2fi−1,3fi−1,4][−∞ci−∞pi−∞pi−∞ci−∞−∞−∞pi−∞−∞−∞ci−∞−∞−∞pi−∞−∞−∞ci−∞]=[fi,0fi,1fi,2fi,3fi,4]\begin{bmatrix} f_{i-1,0} & f_{i-1,1} & f_{i-1,2} & f_{i-1,3} & f_{i-1,4}\end{bmatrix} \begin{bmatrix} -\infty&c_i&-\infty&p_i&-\infty \\ p_i &-\infty &c_i &-\infty &-\infty \\-\infty&p_i &-\infty &-\infty &-\infty \\c_i &-\infty&-\infty&-\infty &p_i \\ -\infty &-\infty &-\infty &c_i &-\infty\end{bmatrix} = \begin{bmatrix}f_{i,0} & f_{i,1} & f_{i,2} & f_{i,3} & f_{i,4}\end{bmatrix}
然后就是 P4719 【模板】动态 DP，使用线段树 + 树链剖分维护即可，复杂度 O(k3qlog⁡2n)\mathcal O(k^3 q \log^2 n)，实际跑得挺快的。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1e16;
int n,q,c[N],p[N],f[N][25],dep[N],fa[N],dfn[N],sz[N],top[N],son[N],rev[N],tot;
vector<int>edge[N];
void dfs1(int u){
	sz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(int v:edge[u])
		if(v!=fa[u]){
			f[v][0]=fa[v]=u; 
			dfs1(v);
			sz[u]+=sz[v];
			if(sz[v]>sz[son[u]]) son[u]=v;
		}
}
void dfs2(int u,int t){
	top[u]=t;
	rev[dfn[u]=++tot]=u;
	if(!son[u]) return;
	dfs2(son[u],t);
	for(int v:edge[u])
		if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
int getkth(int u,int k){
	int x=u;
	for(int i=20;i>=0;i--)
		if(k&(1<<i)) x=f[x][i];
	return x;
}
int getse(int u,int v){
	if(dfn[v]>=dfn[u]&&dfn[v]<dfn[u]+sz[u]) return getkth(v,dep[v]-dep[u]-1);
	return fa[u];
}
struct matrix{
	int a[5][5];
	matrix(){
		for(int i=0;i<5;i++)
			for(int j=0;j<5;j++) a[i][j]=-inf;
	}
	matrix operator*(matrix b){
		matrix c;
		for(int i=0;i<5;i++)
			for(int j=0;j<5;j++)
				for(int k=0;k<5;k++)
					c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);
		return c;
	}
}T1[4*N],T2[4*N];
void build(int x,int l,int r){
	if(l==r){
		T1[x].a[1][0]=T1[x].a[2][1]=T1[x].a[0][3]=T1[x].a[3][4]=p[rev[l]];
		T1[x].a[3][0]=T1[x].a[0][1]=T1[x].a[1][2]=T1[x].a[4][3]=c[rev[l]];
		T2[x]=T1[x];
		return;
	}
	int mid=(l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	T1[x]=T1[2*x]*T1[2*x+1];
	T2[x]=T2[2*x+1]*T2[2*x];
}
matrix query1(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T1[x];
	int mid=(l+r)/2;
	if(R<=mid) return query1(2*x,l,mid,L,R);
	if(L>mid) return query1(2*x+1,mid+1,r,L,R);
	return query1(2*x,l,mid,L,R)*query1(2*x+1,mid+1,r,L,R);
}
matrix query2(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T2[x];
	int mid=(l+r)/2;
	if(R<=mid) return query2(2*x,l,mid,L,R);
	if(L>mid) return query2(2*x+1,mid+1,r,L,R);
	return query2(2*x+1,mid+1,r,L,R)*query2(2*x,l,mid,L,R);
}
matrix qry(int u,int v){
	matrix a,b;
	for(int i=0;i<5;i++) a.a[i][i]=b.a[i][i]=0;
	while(top[u]!=top[v])
		if(dep[top[u]]>dep[top[v]]){
			a=a*query2(1,1,n,dfn[top[u]],dfn[u]);
			u=fa[top[u]];
		}
		else{
			b=query1(1,1,n,dfn[top[v]],dfn[v])*b;
			v=fa[top[v]];
		}
	if(dep[u]>dep[v]) a=a*query2(1,1,n,dfn[v],dfn[u]);
	else b=query1(1,1,n,dfn[u],dfn[v])*b;
	return a*b;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=20;i++)
		for(int j=1;j<=n;j++)
			f[j][i]=f[f[j][i-1]][i-1];
	build(1,1,n);
	for(int u,v;q;q--){
		cin>>u>>v;
		matrix ans;
		ans.a[0][1]=c[u];
		ans.a[0][3]=p[u];
		if(u!=v){
			u=getse(u,v);
			ans=ans*qry(u,v);
		}
		cout<<max({ans.a[0][0],ans.a[0][1],ans.a[0][2],ans.a[0][3],ans.a[0][4]})<<'\n';
	}
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...