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

· · 题解

怎么有这么典的题？

考虑 dp，设 f_{i,0} 表示前 i 个红蓝数量相等的最大值，f_{i,1} 表示前 i 个红比蓝多 1 个的答案，f_{i,2} 表示前 i 个红比蓝多 2 个的答案，f_{i,3} 表示前 i 个蓝比红多 1 个的答案，f_{i,4} 表示前 i 个蓝比红多 2 个的答案，转移非常简单，这里不多赘述。

考虑把这个转移写成矩阵的形式：

\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，使用线段树 + 树链剖分维护即可，复杂度 \mathcal O(k^3 q \log^2 n)，实际跑得挺快的。

代码：


#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;
}