NIO9102 落雨大

我也来到 NOI 了,呢。

郑重声明

本博客内所有与 NOI2019(第 36 届全国青少年信息学奥林匹克竞赛)试题相关之内容,均在对应之机试与复评结束之后发布,详细发布时间与内容可以在 commits 中查看。

Day 499122177

广二宿舍还是没有网.

床边的插座不是一般人能插的..(Orz lbw 插上去了)然而因为有时候要去机房(其实基本上也就刚到那天晚上没事去了..),所以后来还是拔下来了。然后发现不带 220V 转 USB 母头的插头真是个错误的决定..虽然可以用笔记本充电,可如果在寝室门口充电就没法用电脑,所以没法一会儿充电脑用手机、一会儿充手机用电脑。

晚餐有点抽卡的感觉..看名字很难看出拿到手上的到底是什么东西(

吃完晚饭去自习室水了半小时群,然后打短裙 OJ。

切完前两题,好像 rk 5..

然后看 C,问满足一堆条件的个数..一眼容斥..然后真的写了 1h 的容斥 qaq

好不容易过拍了,提交,又 WA 了..

在群里一问,woc,p 不是排列…

5 min 后过了,愉快地垫底了..

过于自闭,看了眼 D,没秒掉,就懒得去想了。

赛后听说 C 可以状压,一想,真的可以状压…..学傻了.webp

Day 557219762

咕掉早饭把火车上剩的吃了。

(开幕式竟然没有 wh 讲话)

灯光打得好!覆盖方位广!给灯光师点个赞!

果然有公开处刑大头照展示,只不过速度比较快,问题不大。

感觉大家喊的口号都听不太清啊..

明 示 爆 零 :

dzd 的讲话中,有这么一段话:

无论何种情况,这个竞赛都会继续下去。因为这个竞赛是正当的,是正义的,合法的。

听到这段话,又想起 ひなた 在桥边含泪喊出的那段话了。

但是,我没有后悔,不能后悔,因为,我所做的事情一定没有错!

(欢迎大家来 Hitokoto 点赞

(当然还有 这句

NOI 可能真的如 dzd 所说,带有一些“净化灵魂”的成分在吧。

最后鸽子蛋破不开,明示摆脱不了爆零的命运

(离场后目击 dzd 被采访)

中餐感觉海星..还是得看看别人买到的是什么再选。(千万不要用排除法来选

中午写了写博客,做了遍笔试,睡了会儿觉。

还是感觉好方..毕竟被鄙视用的错误选项从来没变过(

结果笔试挺水的..题目和题库里完全一样(没有之前在 vfk 博客里看见的“那道题不选 foobar.sh”之类的情况),很多题都不是四个选项而是更少,所以没有任何奇怪的错误选项..

Day 1

看到 T1 就很快想出了 70 分的拆点做法,写完之后几乎一遍过了大样例。

然后去把 T2 和 T3 的 20 + 28 写了,此时 $1.5h​$ 左右。

然后去写 T1 $A=0$ 的部分分,各种写挂写了接近 $2h$..

然后感觉 T2 还是没什么想法,T3 想了几个假贪心,又想了几个假网络流,最后还剩半小时的时候想到了一个考后才叉掉的 $n^3\log$ 的假贪心(讲题时发现稍微改动一下就是正确的 40 分做法..),幸好没写完,不然万一过了样例就 GG 了。

出来之后发现大家都 $148​$ 起步..T1 有正解的,但还有一堆利用数据范围改小的,以及一堆 $70​$ 分算错复杂度的。

T1 我写的数据分治是不可能 $85​$ 以上的,所以特别怕 $70​$ 分做法最后 $90​$ 或者 $95​$。

然后下午一看,我自己倒是没挂分,$85+20+28=133​$,可其它和我写一样东西的都是 $100+20+40​$..

T1 数据范围不知道是不是为了防止爆 int 而改小就算了,复杂度完全错误的 $70​$ 分做法竟然直接 A 了..就很自闭。T3 其他人的 $n^4​$ 常数比我小一截,我也不好说什么..只不过那些“数据有梯度”的出题人凭什么不多给几档部分分啊?

感觉还是赛制问题啊..没有 Subtask 并且现场评测的 OI 赛制出题人也很无奈吧..

把 NOI 嘉年华咕了(玩一些体育运动之类的游戏得奖品什么的),回寝室躺了一会儿,又看了一遍 四色的NOI,感觉自己的心境和 vfk Cu 那年挺像的..只不过就算把 vfk Fe 那年去掉,我也比 vfk 少一年啊..

讲题的话..放一张 T2 讲题的图吧:

Day 116195171

今天是社会活动日。

听说真的有人没去..不知道会不会扣分。

坐 D7 的被奶了:

在博物馆先打了把四人南,然后去随便逛了半个小时。

暗示 route 数据水:

暗示 Day 2 Au 线 30 Ag 线 20:

假毛请大家自行脑补假毛在风中打转的样子

晚上是 zzq 和象的见面会,感觉还是象比较励志,其它三名国家队都是小学开始学的..刷题量好像非常恐怖,而“好好打模拟赛”对我来说几乎不需要解释..我知道平时我是怎样在打模拟赛的,“这个知识点还没学”,“这题没意思”,“题解看不懂”,“这题太简单了,只是考场 sb 了而已,懒得写”,“我先按我的计划补知识点,模拟赛不重要”,最后一题都没有改。这样的话我又在渴求什么呢。

以为自己很努力了,但是不知为何还是系统告诉我:Mission Failed. Play Again.

不知道原因。

张着嘴巴我可以说出一堆:经验少啦,在弱省啦,题做得少啦,数学太弱啦……

但是这是不是真正的原因?怎样解决?

天地无言。

—— vfk《四色的NOI》

可我甚至不能“以为自己很努力了”。

Day 2

今天的纸质题面考前是正面朝上的。

果然有交互,还依然是 I 君。

等等,T2 斗主地?

等等,T1 128MB?简洁数据结构.pdf

开始考试,T1,线段树优化连边?爆空间。88 可能能卡过?感觉很难卡,还得数据分治,写了不到 5min 就放弃了,去写了 72 分。

T2,dp 算洗牌前是 $i​$ 洗牌后是 $j​$ 的概率,第四个点矩阵快速幂,很快就写完了,一遍过样例。这个时候两小时多一点。

考前就想着靠交互翻盘了,还剩接近 3h 肝交互,感觉海星。

这个数据范围好像不太统一啊..既然强制数据分治的话不如会一档写一档好了。

先把 $\mathcal O(n^2)$ 次询问的写了,一开始还写错了,写成了 $n$ 次修改,差点挂掉 $8$ 分。

然后想了一会儿想到了性质 $A$ 一个期望 $\log$ 的做法。写完 + 调完之后 3h 多一点。

然后开始想 T3 各种各样的部分分,乱搞了 2h 一无所获。

出来之后发现大家 T1 都会 K-D Tree,又听说 T2 结论题可以打表..感觉 Ag 基本上没了啊。

我博客用模 998244353 的等比数列,是不是暗示 T2 模 998244353 等差数列,会被禁赛啊。

下午看成绩,$72+30+36=138$,发现 T2 30,原因是 a 数组开小了…只不过不挂分应该也是 Cu,问题不大

讲题的时候松松松把 NOI 弄成了鸭子营。

T2 出题人表示:不止要让训练有素的选手进队,也要让那些能够发现题目性质的选手进队。感觉要是不能打表的话这样的想法也挺有道理的..

出排名,果然 Cu 了。

HB 只有 jxl 和 lwc Ag。只不过两个 E 都上了 Ag 分数线。

zyy 捧杯了,zzy rk2,zzq rk3,_rqy rk4,jumpmelon rk6,myh rk7,zhf rk19。

看到熟悉的名字进集训队的感觉真的很奇妙。

晚上去高校宣讲看热闹。

清华那位老师的气质真的就完全不一样(之前 THUWC 和 THUSC 的时候就体会地非常明显了),有条不紊地讲出硬核的优点(而不是那些花里胡哨的东西)(也没有一种”我是来完成任务“的感觉)(也不会说“那我今天就用这个 PPT 来讲一下”“那我就不用 PPT 了”这样的话),感觉讲了非常多,最后正好卡时讲完了(其它学校都感觉没讲啥就匆匆忙忙结束了)(只不过这也可能是学校实力原因)。(顺带一提,THU 没用 PPT)

北大:我准备了一个 PPT,发邮件的时候挂了,今天我把 PPT 带过来了,我是干讲还是用 PPT,你们觉得怎么样比较好?

主持人:抱歉,请遵守规则口头讲。

北大:我觉得准备这么一个 PPT 不给大家看实在是对不起大家。

(说着就打开了 PPT)

???

天津大学很快就讲完了,然后说“不用打铃了”,很多人鼓掌..感觉 THU 那样打铃的同时有条不紊地结束才比较帅啊(

感觉武大也讲的海星,也是真的在讲而不是完成任务,感觉比较自然。

华东师范大学:男生们可以和很多文科的女生交流。女生们也不要担心,因为你们也可以和很多文科的女生交流。emm…

排在最后的三个学校直接咕了…

只不过我一个 Cu 凭什么评价高校宣讲啊。

“我也是有约的人了!”「两年 OI 换一纸签约」—— 一名拿到人大一等约的我省高二选手。

好像还有面试到晚上十二点,最后拿到“替补二等约”的选手..

看到身边的人退役更是一种说不出的感觉。

Day 232390342

早上咕掉嘉年华,去机房把 D1T1 写了,然后试图学习 k-d tree。

感觉资料还是太少了,也不知道网上那些复杂度是不是对的..

下午闭幕式。大家该 AuAu,该捧的捧该扫射的灯光师继续扫射

结束之后真的落雨大了..下了一个多小时的大雨,选手袜子没了

我双色 NOI 的第一色,是古铜色的。

Day 4

本来不想写 Day 4 的,但广州南的便利店竟然没有泡面,必须得吐槽一下

G1114 竟然没有插座,更得吐槽了

那么,长沙一中再会。

题解

估计会比较咕

D1T1

“去年 D1T1 最短路,今年也是呢”选手自闭了。

出考场听说斜率优化,以为是斜率优化预处理等待时间的连边然后跑最短路。

看了题解才知道原来这题根本不用最短路,连 DAG 最短路都不用..

把边按结束时间($q_i$)排序,令 $f_i$ 表示走完第 $i$ 条边后还需要的烦躁值的最小值。

$\begin{aligned}f_i&=\min\limits_{p_j\ge q_i,x_j=y_i}\{A(p_j-q_i)^2+B(p_j-q_i)+C+q_j-q_i+f_j\}\\&=\min\limits_{p_j\ge q_i,x_j=y_i}\{Ap_j^2+Bp_j+q_j+f_j-2Ap_jq_i\}+Aq_i^2-Bq_i+C-q_i\end{aligned}​$

然后就可以斜率优化了。(因为转移有 $x_j=y_i$ 的限制,要开 $n$ 个双端队列,但不要开 deque,开大量 deque 是会 MLE 的。写法的话,用 vector 存,普通方法写就好了。)

参考代码

按理来说题解里不应该包含模板,只不过这也不是什么官方题解,我就懒得换成正常写法了。

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
#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>

#define int LoveLive
//#define FAST_IOSTREAM 1

#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define ms(a,x)memset(a,x,sizeof(a))
#define fi first
#define se second
#define pq priority_queue
#define pb emplace_back
#define isinf(x)(x>=INF?-1:x)
#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
using namespace std;typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
const double eps=1e-9;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint
(int l,int r){return(int)rng()%(r-l+1)+l;}
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename
T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T&x){cin>>x;}long long
read(){char c;long long out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c
=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T
>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double
&x){scanf("%lf",&x);return x;}void read(char*x){scanf("%s",x);}template<typename T>typename enable_if
<!is_integral<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<
is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write
(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf"
,x);}void write(const char*x){printf("%s",x);}
#endif
template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename
...Args>void read(char*x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename
enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value ||(
is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const
<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)
read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename
iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){
for(;__first!=__last;++__first){write(*__first);sp;}}template<typename InputIt,typename=typename enable_if
<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void
wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}void wts(const
char*x){write(x);sp;}void wtb(const char*x){write(x);br;}void wte(const char*x){write(x);exit(0);}template
<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template
<typename T>void wte(const T&x){write(x);exit(0);}template<typename...Args>void wts(const char*x,Args
...args){wts(x);wts(args...);}template<typename...Args>void wtb(const char*x,Args...args){wts(x);wtb(
args...);}template<typename...Args>void wte(const char*x,Args...args){wts(x);wte(args...);}template<typename
T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...
Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte
(const T&x,Args...args){wts(x);wte(args...);}template<typename T>inline bool up(T&x,const T&y){return
x<y?x=y,1:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}

const int N = 100010;
const int M = 200010;

int n, m, a, b, c, id[M];

struct Edge
{
int u, v, p, q, f;
bool operator<(const Edge & b) const
{
return q > b.q;
}
} e[M];

struct Point
{
int x, y;
Point(int j = 0): x(2 * a * e[j].p), y(a * e[j].p * e[j].p + b * e[j].p + e[j].q + e[j].f) {}
friend bool cmp(const Point & a1, const Point & a2, const Point & a3)
{
if (a1.x == a2.x) return a1.y < a2.y;
return (a1.y - a3.y) * (a2.x - a3.x) >= (a2.y - a3.y) * (a1.x - a3.x);
}
int cal(int k) const { return y - k * x; }
};

struct Deque
{
vector<Point> q;
int ql, qr;
Deque()
{
q.resize(1);
ql = 1;
qr = 0;
}
bool empty() const { return ql > qr; }
void push_back(const Point & x)
{
++qr;
if (q.size() == qr) q.push_back(x);
else q[qr] = x;
}
void cal(int i)
{
while (ql < qr && q[ql + 1].cal(e[i].q) <= q[ql].cal(e[i].q)) ++ql;
e[i].f = q[ql].cal(e[i].q) + a * e[i].q * e[i].q - b * e[i].q + c - e[i].q;
}
void insert(const Point & x)
{
while (ql < qr && cmp(x, q[qr], q[qr - 1])) --qr;
push_back(x);
}
} q[N];

signed main()
{
#ifdef FAST_IOSTREAM
cin.sync_with_stdio(false);
cin.tie(0);
#endif

read(n, m, a, b, c);

For (i, 1, m) read(e[i].u, e[i].v, e[i].p, e[i].q);
++m;
e[m].u = 0;
e[m].v = 1;
e[m].p = 0;
e[m].q = 0;
sort(e + 1, e + m + 1);

For (i, 1, m) id[i] = i;
sort(id + 1, id + m + 1, [](int x, int y) { return e[x].p > e[y].p; });
int idp = 1;

For (i, 1, m)
{
if (e[i].v == n)
{
e[i].f = 0;
continue;
}
while (idp <= m && e[id[idp]].p >= e[i].q)
{
if (e[id[idp]].f < INF) q[e[id[idp]].u].insert(Point(id[idp]));
++idp;
}
if (q[e[i].v].empty())
{
e[i].f = INF;
continue;
}
q[e[i].v].cal(i);
}

For (i, 1, m) if (e[i].u == 0) wte(e[i].f);

return 0;
}

D1T3

其实可以模拟费用流,但如果你写一篇模拟费用流的题解,会发现那是一篇费用流建图的题解和一篇贪心题解拼起来。所以下面是一篇纯贪心题解。

我们要从两个序列中各选 $k$ 个下标,考虑每一步(选择一组下标):

  • 如果还允许选两个不一样的下标,那就从剩下还没选的数里选最大的 $a$ 和最大的 $b$。
  • 如果无法选择不一样的下标了,那么有三种选择:
    1. 选择一组 $a_i+b_i$(即 $a$, $b$ 下标相同)
    2. $a_i$ 被选了,$b_i$ 没有被选,那么把 $a_i$ 与 $b_i$ 匹配,再给 $a_i$ 原来匹配的那个 $b_j$ 找到一个剩下的里面最大的 $a_k$,然后把 $b_j$ 和 $a_k$ 匹配。
    3. 把第二条的 $a$ 和 $b$ 互换。

那么,维护剩下的最大的 $a$,剩下的最大的 $b$,剩下的最大的 $a+b$,$a_i$ 已匹配的最大的 $b_i$,$b_i$ 已匹配的最大的 $a_i$,剩余可选择的不一样下标个数,每个数匹配的数,就可以完成这个贪心了。

前三个最大值排序即可,后两个最大值使用堆维护。细节有些多,写的时候注意每一步都确保每个量正确更新了。尤其需要注意的是“剩余可选择的不一样下标个数”的更新。

参考代码
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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int read()
{
int out = 0;
char c;
while (!isdigit(c = getchar()));
for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
return out;
}

typedef pair<int, int> pii;

const int N = 200010;
const int INF = 1e9;

int T, n, k, dif, a[N], b[N], ida[N], idb[N], idab[N], pa, pb, pab, fa[N], fb[N]; // dif 是剩余可选择的不一样下标个数,id 是用来排序的,pa,pb,pab 记录用到了第几个值(即当前最大值是 a[pa] 之类的),fa,fb 分别记录 a_i 和 b_i 匹配的数的下标
priority_queue<pii> sa, sb, emptypq; // sa 是 b 已匹配的 a,sb 是 a 已匹配的 b,emptypq 是用来多测清空的

void link(int u, int v) // 匹配两个数
{
--dif;
fa[u] = v;
fb[v] = u;
if (u == v) --dif; // 去重,否则会在下面三行代码里加两次
if (fb[u]) ++dif;
else sb.push(pii(b[u], u));
if (fa[v]) ++dif;
else sa.push(pii(a[v], v));
}

void cut(int u, int v) // 断开匹配
{
++dif;
if (fb[u]) --dif;
if (fa[v]) --dif;
if (u == v) ++dif; // 去重
fa[u] = fb[v] = 0;
}

pii geta() // 获取当前剩余的最大 a
{
while (fa[ida[pa]]) ++pa;
return pii(a[ida[pa]], ida[pa]);
}

pii getb() // 获取当前剩余的最大 b
{
while (fb[idb[pb]]) ++pb;
return pii(b[idb[pb]], idb[pb]);
}

pii getab() // 获取当前剩余的最大 a + b
{
while (pab <= n && (fa[idab[pab]] || fb[idab[pab]])) ++pab;
return pii(pab <= n ? a[idab[pab]] + b[idab[pab]] : -INF, idab[pab]);
}

pii getsa() // 获取 b 已选的最大 a
{
while (!sa.empty() && fa[sa.top().second]) sa.pop();
return sa.empty() ? pii(-INF, 0) : sa.top();
}

pii getsb() // 获取 a 已选的最大 b
{
while (!sb.empty() && fb[sb.top().second]) sb.pop();
return sb.empty() ? pii(-INF, 0) : sb.top();
}

int main()
{
T = read();

while (T--)
{
pa = pb = pab = 1;
sa = sb = emptypq;
memset(fa, 0, sizeof(fa));
memset(fb, 0, sizeof(fb));

n = read();
k = read();
dif = k - read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) b[i] = read();

for (int i = 1; i <= n; ++i) ida[i] = idb[i] = idab[i] = i;
sort(ida + 1, ida + n + 1, [](int x, int y){return a[x] > a[y];});
sort(idb + 1, idb + n + 1, [](int x, int y){return b[x] > b[y];});
sort(idab + 1, idab + n + 1, [](int x, int y){return a[x] + b[x] > a[y] + b[y];});

while (k--)
{
if (dif) link(geta().second, getb().second);
else
{
pii nab = getab();
pii na_a = getsa();
pii na_b = getb();
pii nb_a = geta();
pii nb_b = getsb();
if (nab.first >= na_a.first + na_b.first && nab.first >= nb_a.first + nb_b.first) link(nab.second, nab.second);
else if (na_a.first + na_b.first >= nb_a.first + nb_b.first)
{
int t = fb[na_a.second];
cut(t, na_a.second);
link(t, na_b.second);
link(na_a.second, na_a.second);
}
else
{
int t = fa[nb_b.second];
cut(nb_b.second, t);
link(nb_a.second, t);
link(nb_b.second, nb_b.second);
}
}
}

long long ans = 0;
for (int i = 1; i <= n; ++i) ans += (fa[i] ? a[i] : 0) + (fb[i] ? b[i] : 0);
printf("%lld\n", ans);
}

return 0;
}