猫娘的矩阵写得比题解好看(╯▔皿▔)╯

前置：动态 dp

建议去 lgP4719 或者本 ojP1289 学习

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 1e5 + 10;
const int inf = 1e16;
 
// 输入数据：c[i] 红权值，p[i] 蓝权值
int n, q, c[N], p[N];
 
int f[N][25];   
int dep[N], fa[N]; 
int dfn[N], siz[N], top[N], son[N], id[N], tsp;
vector<int> G[N];
#define lc(p) (p << 1)
#define rc(p) ((p << 1) | 1)
 
void dfsa(int u) {
    siz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for (int v : G[u]) {
        if (v != fa[u]) {
            f[v][0] = fa[v] = u;
            dfsa(v);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) son[u] = v;
        }
    }
}
 
void dfsb(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++tsp;
    id[dfn[u]] = u;
    if (!son[u]) return;
    dfsb(son[u], tp);
    for (int v : G[u]) {
        if (v != fa[u] && v != son[u])
            dfsb(v, v);
    }
}
 
// 求 u 向上走 k 步的祖先
int getkth(int u, int k) {
    for (int i = 20; i >= 0; --i)
        if (k & (1 << i)) u = f[u][i];
    return u;
}
 
// 若 v 在 u 的子树内，返回 u 的儿子中指向 v 的那个（即路径上下一个节点）
// 否则返回 fa[u]（路径需要向上走）
int getse(int u, int v) {
    if (dfn[v] >= dfn[u] && dfn[v] < dfn[u] + siz[u])
        return getkth(v, dep[v] - dep[u] - 1);
    return fa[u];
}
 
/*
   状态编号对应差值 d = 红点数 - 蓝点数：
   0: d=0
   1: d=1
   2: d=2
   3: d=-1
   4: d=-2
   合法范围 [-2, 2]
*/
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;
    }
    // max-plus 矩阵乘法
    Matrix operator*(const Matrix &b) const {
        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 维护正序（左->右），T2 维护逆序（右->左）
Matrix T1[4 * N], T2[4 * N];
 
// 建树：叶子节点为单个点的转移矩阵
void build(int x, int L, int R) {
    if (L == R) {
        int u = id[L];
        // 根据状态编号填入转移值
        // 蓝转移：d -> d-1
        T1[x].a[1][0] = p[u]; // d=1 -> d=0
        T1[x].a[2][1] = p[u]; // d=2 -> d=1
        T1[x].a[0][3] = p[u]; // d=0 -> d=-1
        T1[x].a[3][4] = p[u]; // d=-1 -> d=-2
        // 红转移：d -> d+1
        T1[x].a[3][0] = c[u]; // d=-1 -> d=0
        T1[x].a[0][1] = c[u]; // d=0 -> d=1
        T1[x].a[1][2] = c[u]; // d=1 -> d=2
        T1[x].a[4][3] = c[u]; // d=-2 -> d=-1
        T2[x] = T1[x];
        return;
    }
    int MID = (L + R) >> 1;
    build(lc(x), L, MID);
    build(rc(x), MID + 1, R);
    // T1：左子树 × 右子树（深度递增顺序）
    T1[x] = T1[lc(x)] * T1[rc(x)];
    // T2：右子树 × 左子树（深度递减顺序）
    T2[x] = T2[rc(x)] * T2[lc(x)];
}
 
// 查询区间 [l, r] 的正序乘积（深度递增）
Matrix query1(int x, int L, int R, int l, int r) {
    if (l <= L && R <= r) return T1[x];
    int MID = (L + R) >> 1;
    if (r <= MID) return query1(lc(x), L, MID, l, r);
    if (l > MID) return query1(rc(x), MID + 1, R, l, r);
    return query1(lc(x), L, MID, l, r) * query1(rc(x), MID + 1, R, l, 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) >> 1;
    if (r <= MID) return query2(lc(x), L, MID, l, r);
    if (l > MID) return query2(rc(x), MID + 1, R, l, r);
    return  query2(rc(x), MID + 1, R, l, r) * query2(lc(x), L, MID, l, r);
}
 
// 查询路径 u -> v 的转移矩阵（u 和 v 是原始点，路径按从 u 到 v 的顺序）
Matrix qry(int u, int v) {
    Matrix a, b; // 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]]) {
            // u 所在重链更深，从 u 向上到 top[u] 是逆序（深度递减）
            a = a * query2(1, 1, n, dfn[top[u]], dfn[u]);
            u = fa[top[u]];
        } 
        else {
            // v 所在重链更深，从 top[v] 向下到 v 是正序（深度递增）
            b = query1(1, 1, n, dfn[top[v]], dfn[v]) * b;
            v = fa[top[v]];
        }
    }
 
    // 现在在同一条重链上
    if (dep[u] > dep[v]) {
        // u 更深，从 u 向上到 v 是逆序
        a = a * query2(1, 1, n, dfn[v], dfn[u]);
    } 
    else {
        // v 更深（或相等），从 u 向下到 v 是正序
        b = query1(1, 1, n, dfn[u], dfn[v]) * b;
    }
 
    // 最终总转移矩阵 = a * b
    return a * b;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.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;
        G[u].push_back(v);
        G[v].push_back(u);
    }
 
    dfsa(1);
    dfsb(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);
 
    while (q--) {
        int u, v;
        cin >> u >> v;
 
        // ans 作为行向量：初始差值 d = 0（状态0）
        // 但为了方便，我们直接构造处理完第一个点 u 之后的行向量
        // 即从状态 0 出发，选择红色或蓝色后的结果
        Matrix ans;
        ans.a[0][1] = c[u]; // 染红 → 差值+1 → 状态1
        ans.a[0][3] = p[u]; // 染蓝 → 差值-1 → 状态3
 
        if (u != v) {
            // 获取路径上下一个点（即 u 的孩子或父亲）
            int nxt = getse(u, v);
            // 将剩余路径的转移矩阵乘上
            ans = ans * qry(nxt, v);
        }
 
        // 最终答案：取行向量中五个状态的最大值
        int res = max({ans.a[0][0], ans.a[0][1], ans.a[0][2], ans.a[0][3], ans.a[0][4]});
        cout << res << '\n';
    }
 
    return 0;
}

怎么有这么典的题？

考虑 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$ 个的答案，转移非常简单，这里不多赘述。

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

然后就是 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;
}