翻车笔记_ [PA2014]Fiolki [LCA, 清奇脑回路, 翻车]

对着没有错的数据也Debug一下是好习惯

懵逼的 题目

扯淡的 题解

不会, 这题不会

超神模拟我都想了…

看CA爷爷的一句话题解…排序LCA…哦…艹, 我SB了…

于是我就按照一个瓶子加到另一个瓶子建树…按照给定的反应求LCA, 然后按照深度排序…

WAWAWAWAWA…

看到了DaD3zZ学长的题解…Emmmmm要新建节点…为啥啊QAQ…然后就弃掉了…

后来发现…艹, 我个SB

GG

然后…重构代码…新建节点, 找LCA, 按照倒入瓶子的顺序建树…按照深度排序…

WAWAWAWA…

Emmmmm?

查了一天的错没看出来…

然后找拉文迪尔要了数据…调试…Emmmmmm????

dfs的时候我™把dq写成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
/**************************************************************
Problem: 3712
User: Cansult
Language: C++
Result: Accepted
Time:22500 ms
Memory:116320 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (400000 + 5)
#define MAXL (21 + 1)
#define MAXK (500000 + 5)
#define int LL
#define LL long long
using namespace std;
struct edg
{
int to, next;
}b[MAXN << 1];
struct node
{
int x, y, lca, pri;
}sora[MAXK];
int d[MAXN][MAXL], deep[MAXN], m, k, n, lgn, g[MAXN], cntb = -1, a[MAXN], ans, now[MAXN], root, col[MAXN];
void dfs(int dq, int de, int dqc)
{
col[dq] = dqc;
deep[dq] = de;
for (int i = 1; i <= lgn; i++)
d[dq][i] = d[d[dq][i - 1]][i - 1]; // 这个地方的dq...我写成i了...
for (int i = g[dq]; ~i; i = b[i].next)
if (b[i].to != d[dq][0])
d[b[i].to][0] = dq, dfs(b[i].to, de + 1, dqc);
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].to = to;
g[from] = cntb;
}
int lg(int x)
{
int re = 0;
for (; (1 << re) <= x; re++)
continue;
return re;
}
int lca(int x, int y)
{
if (deep[x] < deep[y])
swap(x, y);
for (int i = lgn; i >= 0; i--)
if (deep[d[x][i]] >= deep[y])
x = d[x][i];
if (x == y)
return x;
for (int i = lgn; i >= 0; i--)
if (d[x][i] != d[y][i])
x = d[x][i], y = d[y][i];
return d[x][0];
}
bool cmp(node x, node y)
{
if (deep[x.lca] == deep[y.lca])
return x.pri < y.pri;
return deep[x.lca] > deep[y.lca];
}
main()
{
// cout << "Hello world!" << endl;
memset(g, -1, sizeof(g));
scanf("%lld%lld%lld", &n, &m, &k);
lgn = MAXL - 1;
root = n;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]), now[i] = i;
for (int i = 1; i <= m; i++)
{
int srx, sry;
scanf("%lld%lld", &srx, &sry);
++root;
adn(root, now[srx]);
adn(root, now[sry]);
now[srx] = now[sry] = root;
}
for (int i = root; i; i--)
if (!col[i])
d[i][0] = i, dfs(i, 1, ++col[0]);
for (int i = 1; i <= k; i++)
{
scanf("%lld%lld", &sora[i].x, &sora[i].y);
if (col[sora[i].x] == col[sora[i].y])
sora[i].lca = lca(sora[i].x, sora[i].y);
sora[i].pri = i;
}
sort(sora + 1, sora + k + 1, cmp);
for (int i = 1; i <= k; i++)
{
if (col[sora[i].x] != col[sora[i].y])
continue;
int dq = min(a[sora[i].x], a[sora[i].y]);
a[sora[i].x] -= dq, a[sora[i].y] -= dq;
ans += dq;
}
printf("%lld", ans << 1);
}

/*
46
*/

By 康复中的 死宅 Cansult