难以描述的痛苦。。
我们先预处理出边权大于等于x的边形成的最小生成树或最小生成森林，这些边用主席树存。
那么，如何维护呢，我们从边权从大到小枚举，每次在原来基础上新加一条边后，如果产生了环，就把环中最大的边删去。这样就可以用主席树来维护。
然后对于每个询问l，r，我们只要在root[l]这棵主席树上求边权小于等于r的边权和，这很容易吧。。
这样本题就结束了。orz Gold_7 first blood!!!
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,q,A,p,d,edgenum,cnt,Max,l,r,ans;
int vet[2000010],next[2000010],head[2000010],a[2000010],f[2000010],flag[2000010],root[2000010],e[2000010],dis[2000010];
struct tree{int l,r,sum;}tr[20000010];
struct node{int x,y,z;}ed[2000010];
bool cmp(const node a,const node b){return a.z<b.z;}
int getfather(int x){if (x!=f[x]) f[x]=getfather(f[x]);return f[x];}
void change(int &p,int l,int r,int x,int val)
{
tr[++cnt]=tr[p];p=cnt;tr[p].sum+=val;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) change(tr[p].l,l,mid,x,val);else change(tr[p].r,mid+1,r,x,val);
}
int ask(int p,int l,int r,int x)
{
if (r<=x) return tr[p].sum;
int mid=(l+r)>>1;
if (x<=mid) return ask(tr[p].l,l,mid,x);else return ask(tr[p].l,l,mid,x)+ask(tr[p].r,mid+1,r,x);
}
void add(int u,int v,int w)
{
edgenum++;
vet[edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
dis[edgenum]=w;
}
int dfs(int u,int t,int fa)
{
if (u==t&&fa!=-1) return 1;
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if ((e+1)/2==fa) continue;
if (dfs(v,t,(e+1)/2)){flag[(e+1)/2]=1;return 1;}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].z);
sort(ed+1,ed+m+1,cmp);
for (int i=1;i<=n;i++) f[i]=i;
for (int i=1;i<=m;i++) e[i]=ed[i].z;
for (int i=m;i>=1;i--)
{
root[i]=root[i+1];
if (getfather(ed[i].x)!=getfather(ed[i].y))
{
f[getfather(ed[i].x)]=getfather(ed[i].y);
a[++a[0]]=i;
change(root[i],1,m,i,ed[i].z);
}else
{
Max=-1;
edgenum=0;
for (int j=1;j<=n;j++) head[j]=0;
for (int j=1;j<=a[0];j++)
{
add(ed[a[j]].x,ed[a[j]].y,ed[a[j]].z);
add(ed[a[j]].y,ed[a[j]].x,ed[a[j]].z);
}
add(ed[i].x,ed[i].y,ed[i].z);
add(ed[i].y,ed[i].x,ed[i].z);
for (int j=1;j<=edgenum/2;j++)
flag[j]=0;
dfs(ed[i].x,ed[i].x,-1);
for (int j=1;j<=edgenum/2;j++)
if (flag[j]) Max=max(Max,dis[j*2]);
for (int j=1;j<=a[0];j++)
if (ed[a[j]].z==Max&&flag[j])
{
change(root[i],1,m,a[j],-ed[a[j]].z);
for (int k=j;k<a[0];k++) a[k]=a[k+1];
a[0]--;
break;
}
a[++a[0]]=i;
change(root[i],1,m,i,ed[i].z);
}
}
scanf("%d%d",&q,&A);
while (q--)
{
scanf("%d%d",&p,&d);
l=ans*A+p;r=l+d;
l=lower_bound(e+1,e+m+1,l)-e;
r=upper_bound(e+1,e+m+1,r)-e-1;
ans=ask(root[l],1,m,r);
printf("%d\n",ans);
}
}
HHS]ONE@Z2VQY)I`I.png)
。
