资讯详情

洛谷

和同学拼好解拼出了一个轻松爆标的做法，时间复杂度 \(O(q\log n+nk^3\alpha(n))\)，实测洛谷上最慢不超过 0.5s，并且很短。

首先设计矩阵，容易想到直接设计 \(5\times 5\) 的矩阵转移，每个状态表示多了几个红色或多了几个蓝色。

求出每个询问的 LCA 的位置，我直接倍增，所以时间复杂度为 \(O(q\log n)\)，把询问记录在 LCA 上，离线处理。

然后维护一个并查集，将矩阵作为权值进行维护，对于每个询问采用类似路径压缩的方式维护矩阵。

为了方便维护，我采取的方式是，先不给其它点乘上最顶端的矩阵，让每个除了顶端外的点记录类似前缀的矩阵，这样在压缩时只需要乘上原本的顶端即可求出到新的顶端的矩阵。取出矩阵时如果不是顶端，那么再乘上顶端矩阵即可。

时间复杂度 \(nk^3\alpha(n)\) 实现难度并不高。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,a[100005],b[100005],U[100005],V[100005],st[100005][20],dep[100005],fa[100005];
vector<int> e[100005];
long long ans[100005];
struct MT{long long c[5][5];MT(){memset(c,-0x3f,sizeof(c));}MT friend operator*(const MT &a,const MT &b){MT c;for(int i=0;i<5;i++){for(int j=0;j<5;j++){for(int k=0;k<5;k++)c.c[i][j]=max(c.c[i][j],a.c[i][k]+b.c[k][j]);}}return c;}
}I,c1[100005],c2[100005];
vector<int> g[100005];
int LCA(int l,int r){if(dep[l]<dep[r])swap(l,r);for(int i=19;i>=0;i--)if(dep[st[l][i]]>=dep[r])l=st[l][i];if(l==r)return l;for(int i=19;i>=0;i--){if(st[l][i]!=st[r][i]){l=st[l][i];r=st[r][i];}}return st[l][0];
}
void dfs(int p,int f){dep[p]=dep[f]+1;st[p][0]=f;for(int i=1;i<20;i++)st[p][i]=st[st[p][i-1]][i-1];for(int i:e[p])if(i!=f)dfs(i,p);
}
void calc(int x){if(x==fa[x])return;if(fa[x]==fa[fa[x]])return;calc(fa[x]);c1[x]=c1[x]*c1[fa[x]];c2[x]=c2[fa[x]]*c2[x];fa[x]=fa[fa[x]];
}
void dfs2(int p,int f){for(int i:e[p])if(i!=f)dfs2(i,p);MT x;x.c[0][1]=x.c[1][2]=x.c[2][3]=x.c[3][4]=a[p];x.c[1][0]=x.c[2][1]=x.c[3][2]=x.c[4][3]=b[p];c1[p]=c2[p]=I;for(int i:g[p]){int u=U[i],v=V[i];calc(u),calc(v);MT res=(u==fa[u]?c1[u]:c1[u]*c1[fa[u]])*x*(v==fa[v]?c2[v]:c2[fa[v]]*c2[v]);ans[i]=-1e16;for(int j=0;j<5;j++)ans[i]=max(ans[i],res.c[2][j]);}c1[p]=x,c2[p]=x;for(int i:e[p])if(i!=f)fa[i]=p;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);for(int i=0;i<5;i++)I.c[i][i]=0;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1,u,v;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);for(int i=1,u,v;i<=q;i++){cin>>u>>v;U[i]=u,V[i]=v;g[LCA(u,v)].push_back(i);}for(int i=1;i<=n;i++)fa[i]=i;dfs2(1,0);for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';return 0;
}