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

FFTotoro · 2025-11-09 15:31:59 · 题解

典题。首先考虑序列怎么做，f_{i,v} 表示红色的个数比蓝色的个数多 v(-2\le v\le 2) 个时答案的最大值，转移为 f_{i,j+1}\gets f_{i-1,j}+c_i 以及 f_{i,j-1}\gets f_{i-1,j}+p_i，可以用矩阵 (\max,+) 乘法描述。

链上问题考虑树链剖分，但是这里链是有方向的尤其需要注意。由于没有修改，所以使用猫树维护区间矩阵乘积（能够 O(1) 查询）。令 k=5（矩阵大小），时间复杂度 O(k^3n\log n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=5;
typedef array<array<ll,N>,N> S;
const ll I=-1e18;
inline S operator *(const S &a,const S &b){
  S c;
  for(auto &v:c)v.fill(I);
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      for(int k=0;k<N;k++)
        c[i][k]=max(c[i][k],a[i][j]+b[j][k]);
  return c;
} // 矩阵 (max,+) 乘法
inline S e(){
  S a;
  for(auto &v:a)v.fill(I);
  for(int i=0;i<N;i++)
    a[i][i]=0;
  return a;
} // 生成单位矩阵
inline S gen(pii c){
  S a;
  for(auto &v:a)v.fill(I);
  for(int i=0;i<5;i++){
    if(i<4)a[i][i+1]=c.first;
    if(i)a[i][i-1]=c.second;
  }
  return a;
} // 根据 c[i],p[i] 生成转移矩阵
class cat_tree{
  private:
    int k,m;
    vector<vector<S> > v;
    int lcp(int l,int r){
      return l>>32-__builtin_clz(l^r);
    }
    int getl(int x){
      return (x<<k-__lg(x))-m;
    }
  public:
    cat_tree(vector<S> a){
      int n=a.size();
      k=__lg(n)+(__builtin_popcount(n)>1);
      v.resize((m=1<<k)<<1);
      for(int i=0;i<m;i++)
        v[i+m]={i<n?a[i]:e()};
      for(int i=m-1;i;i--){
        v[i].resize(v[i<<1].size()<<1);
        copy(v[i<<1].begin(),v[i<<1].end(),v[i].begin());
        copy(v[i<<1|1].begin(),v[i<<1|1].end(),v[i].begin()+v[i<<1].size());
      }
      for(int i=m-1;i;i--){
        int x=v[i].size()>>1;
        for(int j=x-2;j>=0;j--)
          v[i][j]=v[i][j]*v[i][j+1];
        for(int j=x+1;j<v[i].size();j++)
          v[i][j]=v[i][j-1]*v[i][j];
      }
    }
    S prod(int l,int r){
      if(l==r)return v[l+m][0];
      int x=lcp(l+m,r+m),b=getl(x);
      return v[x][l-b]*v[x][r-b];
    }
}; // 猫树模板
class hld{
  private:
    int n;
    vector<int> f,d,e,h,t,l;
    optional<cat_tree> T,Tr;
    S internal_query(int l,int r,int d){
      return d?Tr->prod(n-r-1,n-l-1):T->prod(l,r);
    } // 链上有向查询
  public:
    hld(vector<vector<int> > g,vector<pii> a)
      :n(g.size()),f(n),d(n),e(n,1),h(n,-1),t(n),l(n){
      auto dfs=[&](auto &&self,int u)->void{
        int mx=0;
        for(int i:g[u])
          if(i!=f[u]){
            d[i]=d[f[i]=u]+1,self(self,i);
            if(e[u]+=e[i];e[i]>mx)mx=e[i],h[u]=i;
          }
      };
      int o=0;
      vector<S> w(n);
      auto decomp=[&](auto &&self,int u,bool b)->void{
        t[u]=b?t[f[u]]:u,w[l[u]=o++]=gen(a[u]);
        if(~h[u])self(self,h[u],true);
        for(int i:g[u])
          if(i!=f[u]&&i!=h[u])self(self,i,false);
      };
      dfs(dfs,0),decomp(decomp,0,false);
      T.emplace(w),reverse(w.begin(),w.end()),Tr.emplace(w);
    }
    S query(int u,int v){
      S cl=::e(),cr=::e();
      while(t[u]!=t[v]){
        if(d[t[u]]>d[t[v]])cl=cl*internal_query(l[t[u]],l[u],1),u=f[t[u]];
        else cr=internal_query(l[t[v]],l[v],0)*cr,v=f[t[v]];
      }
      if(d[u]<d[v])cr=internal_query(l[u],l[v],0)*cr;
      else cl=cl*internal_query(l[v],l[u],1);
      return cl*cr;
    }
}; // 树链剖分模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  vector<pii> a(n);
  for(auto &[c,p]:a)cin>>c;
  for(auto &[c,p]:a)cin>>p;
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  hld h(g,a);
  while(q--){
    int u,v; cin>>u>>v,u--,v--;
    auto s=h.query(u,v);
    cout<<*max_element(s[2].begin(),s[2].end())<<'\n';
  }
  return 0;
}