从 $1$ 到 $m$ 依次考虑每个日期。假设当前正在考虑第 $i$ 天，那么只有第 $i$ 天来访的游客以及指定第 $i$ 天的查询是有用的。将这些游客和查询都提取出来，通过 Kruskal 重构树可以很方便地在 $O(n\log n)$ 的时间内计算出这些查询的答案。
不幸的是，本题还有加边删边操作，无法轻易地动态维护 Kruskal 重构树。解决问题的关键是注意到假设第 $i$ 天有 $t_i$ 个游客、$q_i$ 个询问，那么可以支付 $O((t_i+q_i)\log n)$ 的代价来获取它们对应的节点形成的大小为 $O(t_i+q_i)$ 的虚树，然后在虚树上暴力构建 Kruskal 重构树计算每个询问的答案。
求虚树的方法很多，比如 LCT 或者离线分治。假设 $n,m,p,q$ 同阶，总时间复杂度为 $O(n\log n)$。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005,M=200005,Q=200005,K=19;
vector<int>gt[M],gq[M];
struct Qry{int x;ll ans;}qry[Q];
struct E{int x,y,w;}e[K][N],edge[N];
namespace Inner{
int f[N<<1],tour[N<<1];ll sum[N<<1];
inline bool cmp(const E&a,const E&b){return a.w<b.w;}
int F(int x){
if(f[x]==x)return x;
int y=f[x];
f[x]=F(f[x]);
sum[x]+=sum[y];
return f[x];
}
inline void solve(int n,int m,int d){
int i;
for(i=1;i<=n;i++){
f[i]=i;
tour[i]=sum[i]=0;
}
for(const auto&o:gt[d])tour[o]++;
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++){
int x=edge[i].x,y=edge[i].y,w=edge[i].w;
x=F(x),y=F(y);
int z=n+i;
sum[x]=1LL*w*tour[y];
sum[y]=1LL*w*tour[x];
sum[z]=0;
f[x]=f[y]=f[z]=z;
tour[z]=tour[x]+tour[y];
}
for(const auto&o:gq[d]){
int x=qry[o].x;
F(x);
qry[o].ans=sum[x];
}
}
}
struct Seg{int x,y,w,l,r;}seg[K][N+M];
int n,m,ct,cq,ce,i,x,y,z,o;
int g[N],v[N<<1],w[N<<1],nxt[N<<1],ed,fa[N],wei[N],id[N],vip[N];bool vis[N];
inline void add(int x,int y,int z){
v[++ed]=y;
w[ed]=z;
nxt[ed]=g[x];
g[x]=ed;
}
inline void addedge(int x,int y,int z){
add(x,y,z);
add(y,x,z);
}
inline void newedge(int x,int y,int z){
edge[++ed].x=x;
edge[ed].y=y;
edge[ed].w=z;
}
void compress(int x,int y){
int d=0;
id[x]=0;
vis[x]=1;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
fa[u]=x;
wei[u]=w[i];
compress(u,x);
if(!id[u])continue;
d++;
id[x]^=id[u];
}
if(d>1)vip[x]=1;
if(vip[x]){
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
int t=id[u];
if(!t)continue;
int mx=0;
for(int j=t;j!=x;j=fa[j])if(mx<wei[j])mx=wei[j];
newedge(x,t,mx);
}
id[x]=x;
}
}
void solve(int d,int l,int r,int ce,int n,int m){
int i;
ed=0;
for(i=1;i<=n;i++)vip[i]=vis[i]=g[i]=0;
for(i=1;i<=m;i++)addedge(e[d][i].x,e[d][i].y,e[d][i].w);
for(i=1;i<=ce;i++){
if(seg[d][i].r<l||seg[d][i].l>r)continue;
if(seg[d][i].l<=l&&seg[d][i].r>=r){
addedge(seg[d][i].x,seg[d][i].y,seg[d][i].w);
continue;
}
vip[seg[d][i].x]=vip[seg[d][i].y]=1;
}
for(i=l;i<=r;i++){
for(const auto&o:gt[i])vip[o]=1;
for(const auto&o:gq[i])vip[qry[o].x]=1;
}
ed=0;
for(i=1;i<=n;i++)if(vip[i]&&!vis[i])compress(i,0);
int _n=0;
for(i=1;i<=n;i++)if(vip[i])vip[i]=++_n;
if(_n<=1)return;
n=_n;
m=ed;
for(i=1;i<=m;i++){
edge[i].x=vip[edge[i].x];
edge[i].y=vip[edge[i].y];
}
for(i=l;i<=r;i++){
for(auto&o:gt[i])o=vip[o];
for(const auto&o:gq[i])qry[o].x=vip[qry[o].x];
}
if(l==r){
Inner::solve(n,m,l);
return;
}
int _ce=0;
for(i=1;i<=m;i++)e[d+1][i]=edge[i];
for(i=1;i<=ce;i++){
if(seg[d][i].r<l||seg[d][i].l>r)continue;
if(seg[d][i].l<=l&&seg[d][i].r>=r)continue;
seg[d+1][++_ce].x=vip[seg[d][i].x];
seg[d+1][_ce].y=vip[seg[d][i].y];
seg[d+1][_ce].w=seg[d][i].w;
seg[d+1][_ce].l=seg[d][i].l;
seg[d+1][_ce].r=seg[d][i].r;
}
int mid=(l+r)>>1;
solve(d+1,l,mid,_ce,n,m);
solve(d+1,mid+1,r,_ce,n,m);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>ct>>cq;
for(i=1;i<n;i++){
cin>>x>>y>>z;
seg[0][i].x=x;
seg[0][i].y=y;
seg[0][i].w=z;
seg[0][i].l=1;
seg[0][i].r=m;
}
ce=n-1;
for(i=1;i<=m;i++){
cin>>o>>x>>y>>z;
seg[0][o].r=i-1;
seg[0][++ce].x=x;
seg[0][ce].y=y;
seg[0][ce].w=z;
seg[0][ce].l=i;
seg[0][ce].r=m;
}
for(i=1;i<=ct;i++){
cin>>o>>x;
gt[o].emplace_back(x);
}
for(i=1;i<=cq;i++){
cin>>o>>x;
qry[i].x=x;
gq[o].emplace_back(i);
}
solve(0,1,m,ce,n,0);
for(i=1;i<=cq;i++)cout<<qry[i].ans<<"\n";
}
标签：Mountain,Contest,int,seg,ce,II,vip,continue,include From： https://www.cnblogs.com/clrs97/p/18424674