Chrysanthemum's Blog

难以描述的痛苦。。

我们先预处理出边权大于等于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);
    }
}