JZOJ 5433 图

发表于 | 分类于 |

首先是一个有趣的结论：整张图的最小生成树一定只由两种边分别的导出子图的最小生成树的边组成。
证明可以考虑反证法，留作练习（

以下分别称呼两种边为 A 类边和 B 类边。
于是可以求出 A 类边导出子图的最小生成树和 B 类边导出子图的最小生成树，当 \(x\) 非常小的时候，显然答案就是 A 类边的最小生成树。
当 \(x\) 增大时，会逐渐有 B 类边替换掉最小生成树中的 A 类边。

从而考虑这样一个过程：求出每条 B 类边会在何时替换掉哪条 A 类边，将这些「分界线」排序后离线处理询问即可。
但是这并不好求。

事实上，直接按照 \(k\) 从小到大的顺序求每条 B 类边构成的环上最大的 A 类边就是这条 B 类边最后替换掉的 A 类边。
虽然 B 类边显然并不是从小到大替换 A 类边的，但容易发现按此种顺序处理并不会影响结果。
于是采用 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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5;
const int M = 4e5;
int n,A,B,q;
struct Edge
{
    int u,v,k;
    inline bool operator<(const Edge &o) const
    {
        return k < o.k;
    }
} ea[M + 5],eb[M + 5],a[N + 5];
int val[N + 5];
int fa[N + 5],tot;
inline int get(int x)
{
    return !fa[x] ? x : (fa[x] = get(fa[x]));
}
namespace LCT
{
    #define chk(p) (tr[tr[p].fa].ch[1] == (p))
    #define isson(p) (tr[tr[p].fa].ch[0] == (p) || tr[tr[p].fa].ch[1] == (p))
    struct node
	{
        int fa,val,max;
        int rev;
        int ch[2];
    } tr[N + 5];
    inline void up(int p)
	{
        tr[p].max = max(p,max(tr[tr[p].ch[0]].max,tr[tr[p].ch[1]].max,[](int x,int y)
        {
            return tr[x].val < tr[y].val;
        }),[](int x,int y)
        {
            return tr[x].val < tr[y].val;
        });
    }
    inline void down(int p)
	{
        if(tr[p].rev)
        {
            tr[p].ch[0] && (tr[tr[p].ch[0]].rev ^= 1),
            tr[p].ch[1] && (tr[tr[p].ch[1]].rev ^= 1),
            swap(tr[p].ch[0],tr[p].ch[1]),
            tr[p].rev ^= 1;
        }
    }
    inline void rotate(int p)
	{
        int x = tr[p].fa,y = tr[x].fa,d = chk(p),t = tr[p].ch[d ^ 1];
        isson(x) && (tr[y].ch[chk(x)] = p),
        tr[p].ch[d ^ 1] = x,tr[x].ch[d] = t,
        t && (tr[t].fa = x),
        tr[x].fa = p,tr[p].fa = y,
        up(x),up(p);
    }
    int s[N + 5],top;
    void splay(int p)
	{
        s[top = 1] = p;
        for(register int x = p;isson(x);s[++top] = x = tr[x].fa);
        for(;top;down(s[top--]));
        for(register int x;isson(p);rotate(p))
            x = tr[p].fa,
            isson(x) && (rotate(chk(p) ^ chk(x) ? p : x),1);
    }
    inline void access(int p)
	{
        for(register int x = 0;p;p = tr[x = p].fa)
            splay(p),tr[p].ch[1] = x,up(p);
    }
    inline int findrt(int p)
	{
        access(p),splay(p);
        for(;tr[p].ch[0];p = tr[p].ch[0]);
        splay(p);
        return p;
    }
    inline void makert(int p)
	{
        access(p),splay(p),tr[p].rev ^= 1;
    }
    inline void split(int x,int y)
	{
        makert(x),access(y),splay(y);
    }
    inline void link(int x,int y)
	{
        makert(x),findrt(y) ^ x && (tr[x].fa = y);
    }
    inline void cut(int x,int y)
	{
        makert(x),findrt(y) == x && tr[y].fa == x && !tr[y].ch[0] && (tr[y].fa = tr[x].ch[1] = 0,up(x),1);
    }
}
struct s_query
{
    int v,id;
    inline bool operator<(const s_query &o) const
    {
        return v < o.v;
    }
} qry[N + 5];
long long cur,ans[N + 5];
int main()
{
    freopen("graph.in","r",stdin),freopen("graph.out","w",stdout);
    scanf("%d%d%d%d",&n,&A,&B,&q);
    for(register int i = 0;i <= n;++i)
        LCT::tr[i].val = -0x3f3f3f3f;
    for(register int i = 1;i <= A;++i)
        scanf("%d%d%d",&ea[i].u,&ea[i].v,&ea[i].k);
    for(register int i = 1;i <= B;++i)
        scanf("%d%d%d",&eb[i].u,&eb[i].v,&eb[i].k);
    sort(ea + 1,ea + A + 1);
    for(register int i = 1,fu,fv;i <= A;++i)
    {
        fu = get(ea[i].u),fv = get(ea[i].v);
        if(fu ^ fv)
            a[++tot] = ea[i],cur += ea[i].k,
            LCT::tr[n + tot].val = ea[i].k,LCT::up(n + tot),
            LCT::link(n + tot,ea[i].u),LCT::link(n + tot,ea[i].v),
            fa[fv] = fu;
    }
    sort(eb + 1,eb + B + 1),tot = 0,memset(fa,0,sizeof fa);
    for(register int i = 1,k,fu,fv;i <= B;++i)
    {
        fu = get(eb[i].u),fv = get(eb[i].v);
        if(fu ^ fv)
        {
            fa[fv] = fu,
            LCT::split(eb[i].u,eb[i].v),k = LCT::tr[eb[i].v].max;
            if(k <= n)
                continue;
            val[++tot] = eb[i].k - LCT::tr[k].val,
            LCT::cut(k,a[k - n].u),LCT::cut(k,a[k - n].v),
            LCT::link(eb[i].u,eb[i].v);
        }
    }
    for(register int i = 1;i <= q;++i)
        scanf("%d",&qry[i].v),qry[i].id = i;
    sort(qry + 1,qry + q + 1),sort(val + 1,val + tot + 1);
    for(register int i = 1,j = 0;i <= q;++i)
    {
        for(;j < tot && val[j + 1] - qry[i].v * 2 <= 0;cur += val[++j]);
        ans[qry[i].id] = cur + (long long)qry[i].v * (n - 1 - j * 2);
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}

Gitalking ...