Early's Blog

Hello, World!

0%

「2020-02-28省选模拟赛」小 B 的图

发表于 分类于
本文字数： 4.5k

题目链接

题意

一个由 nn 个点、A+BA+B 条边组成的无向连通图，有一变量 xx，有 AA 条边的权值为 k+xk+x，有 BB 条边的权值为 k−xk-x。保证只保留这 AA 条边或这 BB 条边时图连通。

多组数据，每次询问给定 xx，求此时图的最小生成树权值和是多少。

思路

对于那 AA 条边，它们的相对大小不会变；BB 边同理。

先对 AA 边和 BB 边分别建最小生成树，只有这两个生成树用到的 2n−22n-2 条边是有用的。

易知，当 x→−∞x\to-\infty 时，使用 AA 边的最小生成树；当 x→∞x\to\infty 时，使用 BB 边的最小生成树。

当 xx 从 −∞-\infty 逐渐变大时，会有 BB 边不断代替 AA 边。

越小的 BB 边一定会代替它能代替的最大的 AA 边。

那么，我们就可以从小到大访问每条 BB 边，查询它能代替的权值最大的 AA 边，计算它代替 AA 边时 xx 的临界值，然后在树上删掉这条 AA 边，加入这条 BB 边。

最后把所有临界值排序，查询时二分查找即可。

时间复杂度 O((n+A+B+q)log⁡n)O((n+A+B+q)\log n)。

实现

在树上进行加边 / 删边可以用 LCT 维护。

对 AA 边求最小生成树时用类似 Kruskal 重构树的方法，便于 LCT 维护路径边权最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5,M=2e5,inf=0x3f3f3f3f;
int n,ma,mb,q,m,fa[N+1],mp[M+1],id[N<<1],pos[M+1];
long long sum[M+1];
struct edge {
    int u,v,w;
    inline bool operator<(edge ano)const
    {
        return w<ano.w;
    }
};
edge a[M+1],b[M+1];
struct tree {
    int maxn;
    bool rev;
    tree *fa,*son[2];
};
tree t[N<<1];
inline void idmax(tree *x,tree *y)
{
    if(a[y->maxn].w>a[x->maxn].w) {
        x->maxn=y->maxn;
    }
    return;
}
inline void push_up(tree *x)
{
    x->maxn=id[x-t];
    idmax(x,x->son[0]),idmax(x,x->son[1]);
    return;
}
inline bool is_root(tree *x)
{
    return (x!=x->fa->son[0])&&(x!=x->fa->son[1]);
}
inline bool son_type(tree *x)
{
    return x==x->fa->son[1];
}
inline void push_down(tree *x)
{
    if(!x->rev) {
        return;
    }
    x->son[0]->rev^=1,x->son[1]->rev^=1;
    swap(x->son[0],x->son[1]);
    x->rev=0;
    return;
}
void update(tree *x)
{
    if(!is_root(x)) {
        update(x->fa);
    }
    push_down(x);
    return;
}
void rotate(tree *x)
{
    tree *fa=x->fa,*ffa=fa->fa;
    int typ=son_type(x);
    if(!is_root(fa)) {
        ffa->son[son_type(fa)]=x;
    }
    fa->son[typ]=x->son[typ^1],x->son[typ^1]->fa=fa;
    x->son[typ^1]=fa,fa->fa=x;
    x->fa=ffa;
    push_up(fa),push_up(x);
    return;
}
void splay(tree *x)
{
    update(x);
    for(tree *fa;fa=x->fa,!is_root(x);rotate(x)) {
        if(!is_root(fa)) {
            rotate(son_type(x)==son_type(fa)?fa:x);
        }
    }
    push_up(x);
    return;
}
void access(tree *x)
{
    for(tree *ori=t;x!=t;ori=x,x=x->fa) {
        splay(x);
        x->son[1]=ori;
        push_up(x);
    }
    return;
}
inline void make_root(tree *x)
{
    access(x);
    splay(x);
    x->rev^=1;
    return;
}
inline void split(tree *x,tree *y)
{
    make_root(x);
    access(y);
    splay(y);
    return;
}
void link(tree *x,tree *y)
{
    make_root(x);
    x->fa=y;
    return;
}
void cut(tree *x,tree *y)
{
    split(x,y);
    x->fa=y->son[0]=t;
    return;
}
int find(int x)
{
    return fa[x]?fa[x]=find(fa[x]):x;
}
inline bool merge(int x,int y)
{
    x=find(x),y=find(y);
    return x==y?false:(fa[x]=y,true);
}
long long kruskal()
{
    for(int i=0;i<n<<1;++i) {
        t[i]=tree{0,0,t,{t,t}};
    }
    long long ret=0;
    for(int i=1,cnt=n;cnt!=(n<<1)-1;++i) {
        int u=a[i].u,v=a[i].v;
        if(!merge(u,v)) {
            continue;
        }
        mp[i]=++cnt,id[cnt]=i;
        push_up(t+cnt);
        link(t+u,t+cnt),link(t+v,t+cnt);
        ret+=a[i].w;
    }
    return ret;
}
inline long long calc(int p,int x)
{
    return sum[p]+1ll*(n-(p<<1)-1)*(x-pos[p]);
}
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%d%d%d%d",&n,&ma,&mb,&q);
    for(int i=1;i<=ma;++i) {
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    for(int i=1;i<=mb;++i) {
        scanf("%d%d%d",&b[i].u,&b[i].v,&b[i].w);
    }
    sort(a+1,a+ma+1),sort(b+1,b+mb+1);
    a[0].w=-inf;
    sum[0]=kruskal()<<1;
    for(int i=1,rem=n-1;(i<=mb)&&rem;++i) {
        int u=b[i].u,v=b[i].v;
        split(t+u,t+v);
        if(!t[v].maxn) {
            continue;
        }
        edge *pre=&a[t[v].maxn];
        tree *x=t+mp[t[v].maxn];
        --rem;
        cut(t+pre->u,x),cut(t+pre->v,x);
        link(t+u,t+v);
        pos[++m]=b[i].w-pre->w;
    }
    sort(pos+1,pos+m+1);
    for(int i=1;i<=m;++i) {
        sum[i]=calc(i-1,pos[i]);
    }
    while(q--) {
        int x,p;
        scanf("%d",&x);
        p=upper_bound(pos+1,pos+m+1,x<<=1)-pos;
        printf("%lld\n",calc(p-1,x)>>1);
    }
    return 0;
}