马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
洛谷
和同学拼好解拼出了一个轻松爆标的做法，时间复杂度 \(O(q\log n+nk^3\alpha(n))\)，实测洛谷上最慢不超过 0.5s，并且很短。
首先筹划矩阵，容易想到直接筹划 \(5\times 5\) 的矩阵转移，每个状态表示多了几个红色或多了几个蓝色。
求出每个扣问的 LCA 的位置，我直接倍增，所以时间复杂度为 \(O(q\log n)\)，把扣问记载在 LCA 上，离线处理。
然后维护一个并查集，将矩阵作为权值进行维护，对于每个扣问采用类似路径压缩的方式维护矩阵。
为了方便维护，我采取的方式是，先不给其它点乘上最顶端的矩阵，让每个除了顶端外的点记载类似前缀的矩阵，这样在压缩时只需要乘上原来的顶端即可求出到新的顶端的矩阵。取出矩阵时假如不是顶端，那么再乘上顶端矩阵即可。
时间复杂度 \(nk^3\alpha(n)\) 实现难度并不高。
代码：
[code]#includeusing namespace std;int n,q,a[100005],b[100005],U[100005],V[100005],st[100005][20],dep[100005],fa[100005];vector 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;iq; for(int i=1;i>a; for(int i=1;i>b; for(int i=1,u,v;i>u>>v; e.push_back(v); e[v].push_back(u); } dfs(1,0); for(int i=1,u,v;i>u>>v;U=u,V=v; g[LCA(u,v)].push_back(i); } for(int i=1;i |
发表于 2026-8-16 08:15:11