¶ 记录
赛时有效输出1h 剩余4h推箱子/想h 最后都没做出来 场上只过了AG
¶ 赛后补题
¶ H:Maxmizer
给出两个排列A和B 每次操作可以交换A中相邻两个元素 求出使得a与b每个下标差的绝对值之和最大所需的最小交换次数
注意到大于n/2的元素对应的如果都是小于n/2的元素 则他们的差的绝对值之和是定值 且与最优答案相等(直接逆序)
因此可以考虑转换成01序列来做 让0对应1 1对应0 就能使得答案最大
那最优交换次数怎么求？
把A中的0和B中的1的下标按顺序存起来 计算对应下标的差的绝对值之和就行
为什么？
这样可以做到把0和对应的1连线 他们的连线没有交叉 从而把一个0交换到对应1的位置不会影响其他0的交换
#include<bits/stdc++.h>
using namespace std;
const int maxn = 250007;
#define ll long long
ll Abs(ll _a) {
return _a<0?-_a:_a;
}
ll a[maxn], b[maxn], c[125003], d[125003], e[125003];
int c1, n, c2, d1, d2;
ll ans, ans2;
int main() {
scanf("%d",&n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] <= n/ 2) c[++c1] = i;
if (a[i] <= (n + 1) / 2) d[++d1] = i;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
if (b[i] > n - n / 2) ans += Abs(i - c[++c2]);
if (b[i] > n - (n+1)/2) ans2 += Abs(i - d[++d2]);
}
cout << min(ans, ans2);
}
¶ F. Hilbert's Hotel
询问是独立的, 先看看怎么做吧.
由于给定了组号, 并且各组之间也是独立的, 每组第小的房间号是否可以用一个函数写出来呢? 答案显然是可以! 一开始第组的函数为, 如果新来了个旅客, 那么原来的函数都加上一个, 比如变为, 新来的这一组函数为. 如果新来了无限个旅客, 那么原来的函数都乘以, 比如, , 新来的这一组函数为. 这样对于查询, 就可以很方便地代值计算得到答案了.
结合题意和这些函数, 可以发现, 函数是一次函数. 又由于要对前缀进行区间修改, 可以考虑使用线段树, 那么找一个特定的组号就是单点查询. 进一步发现, 一次函数中, 的系数一定是的次幂, 所以我们在保存节点信息时, 可以保存系数的指数, 以及截距. 答案需要取模, 所以截距可以取模保存. 因为是区间修改, 还需要打个lazy tag.
对于询问, 先来考虑暴力的做法. 直接存哪个房价住的是哪些人是不现实的, 但是我们可以"回溯". 即给出的, 去考虑上一个操作, 如果是入住个人, 那么这个查询就相当于没有上一个操作, 然后查询3 (x-k). 当然如果是负数, 那么显然这个就是属于上一个操作所修改的, 即答案为上一个操作的组号. 入住无限个旅客也是同理, 让除以, 如果是奇数, 那么就是属于上个操作所修改的, 否则就可以看成在上一个操作之前的查询3 x/2. 因为每个操作, 对应每一组, 所以一直回溯, 便可找到相应的组了.
这样复杂度是的, 加上查询就是, 显然不行. 但是这个做法有优化的空间. 如果有一段连续的加, 设他们的和为, 那么就可以直接判断答案是不是在这一段连续的加中. 即, 如果, 则在, 否则不在. 在的话可以二分, 找到具体是哪一个点让他小于. 不在的话, 说明需要再往前找. 连续一段加的前面一个是乘以, 那么首先看的奇偶性, 像之前说的那样判断是找到了还是需要继续回溯.
记录乘以出现的位置, 即可直接找到一段连续的加(见代码p2[]).
维护一段连续的加, 需要的是后缀和. 其实可以在操作的过程中维护前缀和, 后缀和可以通过两个前缀和的差得到.
这样查询的复杂度就只和乘以的次数有关. 每次到乘以的点都会让减半, 那么查询的复杂度就是
需要特别注意的是(或者在回溯的过程中)的情况. 如果此时前面都是乘以的操作, 那么他会一直跑完这些操作, 这样复杂度会被卡成, 所以我们需要特判(或)的情况: 对于连续的乘以, 直接跳到最前面第一个乘以的操作即可. 可在过程中预处理(见代码last_2[], gid[]).
总复杂度
¶ 代码
(过程中需要用到G-1, 所以我的G从开始; 第小是直接代入, 所以, 当然也可以初始化一次函数截距为, 直接代入)
const int maxn = 3e5+10;
const int P = 1e9+7;
int Plus(LL a, LL b) {
return a + b >= P ? (a + b) % P : a + b;
}
int Mult(LL a, LL b) {
return a * b >= P ? a * b % P : a * b;
}
struct SegmentTreeNode {
int l, r, mid, pk, b;
} tree[maxn << 2];
int n, pw[maxn], G = 1, last_2[maxn], cnt = 0, gid[maxn];
LL pre[maxn];
vector<int> p2;
void Build(int v, int l, int r) {
tree[v] = SegmentTreeNode{l, r, (l+r)>>1, 0, 0};
if (l == r)
return;
else {
Build(LCH(v), l, tree[v].mid);
Build(RCH(v), tree[v].mid+1, tree[v].r);
}
}
void Init() {
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = Mult(pw[i-1], 2);
Build(1, 1, n);
}
void UpdateNode(int v, int pk, int b) {
tree[v].b = Mult(pw[pk], tree[v].b);
tree[v].b = Plus(tree[v].b, b);
tree[v].pk += pk;
}
void Down(int v) {
UpdateNode(LCH(v), tree[v].pk, tree[v].b);
UpdateNode(RCH(v), tree[v].pk, tree[v].b);
tree[v].pk = tree[v].b = 0;
}
void Update(int v, int l, int r, int pk, int b) {
if (tree[v].l == l && tree[v].r == r)
UpdateNode(v, pk, b);
else {
Down(v);
if (l > tree[v].mid)
Update(RCH(v), l, r, pk, b);
else if (r <= tree[v].mid)
Update(LCH(v), l, r, pk, b);
else {
Update(LCH(v), l, tree[v].mid, pk, b);
Update(RCH(v), tree[v].mid+1, r, pk, b);
}
}
}
int Query(int v, int p, int x) {
if (tree[v].l == tree[v].r)
return Plus(Mult(pw[tree[v].pk], x), tree[v].b);
Down(v);
if (p > tree[v].mid)
return Query(RCH(v), p, x);
else
return Query(LCH(v), p, x);
}
int main() {
scanf("%d", &n);
Init();
pre[1] = 0;
last_2[1] = -1;
for (int i = 1; i <= n; i++) {
int op;
scanf("%d", &op);
if (op == 1){
int k;
scanf("%d", &k);
if (k) {
Update(1, 1, G++, 0, k);
pre[G] = pre[G-1] + k;
last_2[G] = 0;
}
else {
Update(1, 1, G++, 1, 0);
Update(1, G, G, 1, 1);
pre[G] = 0;
last_2[G] = last_2[G-1] ? last_2[G-1] : G;
gid[G] = cnt++;
p2.push_back(G);
}
}
else if (op == 2){
int g, x;
scanf("%d%d", &g, &x);
printf("%d\n", Query(1, g+1, x-1));
}
//下面写的和狗屎一样丑, 能力有限, 见谅
else {
int x;
scanf("%d", &x);
int cur = G, res = 1, L = 2, R = G, flag = 1;
for (int i = p2.size() - 1; ~i; i--) {
// 等于0也可回溯上一步
if (x - pre[cur] >= 0) {
x -= pre[cur];
if (x & 1) {
res = p2[i];
flag = 0;
break;
}
else {
if (x == 0) {
cur = last_2[p2[i]];
i = gid[cur];
}
x >>= 1;
cur = p2[i] - 1;
R = cur;
}
}
else {
L = p2[i] + 1, R = cur;
break;
}
}
if (flag) {
while (L <= R) {
int mid = (L + R) >> 1;
if (x - (pre[cur] - pre[mid-1]) < 0) {
L = mid + 1;
res = mid;
}
else
R = mid - 1;
}
}
printf("%d\n", res-1);
}
}
return 0;
}
¶ J. Parklife
很自然地(zzs原话), 发现线段只有包含关系, 可以构成一棵树. 我们把最大的线段当成根, 权值为即可. 由于需要对每个都输出答案, 所以可以考虑dp.
先来看这样的一个状态: 表示对于子树, 层次不超过的最大值, 显然不能用这样的方程, 他的复杂度是. 不过我们可以从中考虑一些问题.
当时, 我们把方程写过一下: 表示子树选一层的最大值, 转移方程为:
发现没有, 其实我们在算的时候, 已经"算到了"的值(不管最大值是哪一个, 次大值加上的值[就是这里做出来的最大值]就是的值了), 只不过我们把他"放弃"了. 实际上我们可能还放弃了甚至更多的值(这里也指"增量").
如果把这些值合理利用, 是不是就能够只跑一次了呢?
不妨这样想, 对每一个节点, 开一个大根堆, 维护的是递增取值时的"增量", 即:
- 堆中的第一个元素是取一层得到的值
- 第二个元素是取两层在取一层上多加上的值
- 以此类推
如何维护这样一个堆呢?
和一样, 把这个堆当成的值即可, 它也是从儿子转移过来的. 让儿子的堆的对应位置相加, 然后再把当前节点的丢进去就行了.
证明:
先证儿子对应位置相加的正确性: 由于各个儿子的选择是互相独立的, 而且儿子的堆中元素是排好了序的, 那么对应位置相加以后得到的新序列也是排好了序的, 所以对应位置直接相加即可.
再证丢进去一个可行: 每做一个节点, 都新增一层, 所以把当前的丢进堆里是必要的. 由于子树中, 各深度节点的选择是独立的, 所以根据贪心, 无论在哪一个地方, 只要比子树的某些值更优, 即可选上, 递增的时候再去选其他值(最小当然最后选即可).
做完以后, 根的堆的前缀和就是答案了. 当然堆中元素很可能不满个, 超过堆大小的, 就已经可以全部选上了. 这些的答案就是堆中所有元素的和(其实也就是所有节点的和).
合并堆的时候记得用启发式合并.
还有最后一个问题: 如何建树?
将线段按从小到大, 长度从大到小(实际上可看成, 因为相等才比较)排序, 可以发现, 这个顺序就是树的前序遍历. 开一个栈维护一条链: 如果栈顶线段不包含当前线段, 证明这两个线段不是父子关系, 那么栈顶出栈, 直到栈顶和当前线段是父子关系, 连边. 当前点入栈. 这样就可以建树了.
复杂度小于, 因为启发式合并的跑不满. (官方题解证明了复杂度其实是, 看不懂)
(官方题解太阴间, O(n^2)的dp一顿数学分析, 结果和我的做法一样...)
据说还有长链剖分的算法?? 有空学, 咕咕咕.
¶ 代码
const int maxn = 2.5e5+10;
struct Segment {
int l, r, w;
bool operator < (const Segment &S) const {
return l == S.l ? r > S.r : l < S.l;
}
} segments[maxn];
int n;
vector<int> son[maxn];
vector<int> stk;
void Build() {
stk.push_back(0);
for (int i = 1; i <= n; i++) {
Segment &s = segments[i];
int fa = stk.back();
while (!(segments[fa].l <= s.l && s.r <= segments[fa].r)) {
stk.pop_back();
fa = stk.back();
}
son[fa].push_back(i);
stk.push_back(i);
}
#ifdef D
printf("Tree:\n");
for (int i = 0; i <= n; i++) {
printf("%d:\n", i);
for (auto v : son[i])
printf("%d ", v);
puts("");
}
#endif
}
MaxHeap heap[maxn];
int idx = 0;
// 启发式合并
int Merge(int x, int y) {
vector<LL> pool;
if (heap[x].size() > heap[y].size())
swap(x, y);
while (!heap[x].empty()) {
pool.push_back(heap[x].top() + heap[y].top());
heap[x].pop(), heap[y].pop();
}
for (auto t : pool)
heap[y].push(t);
return y;
}
// 返回的是当前点的堆(的下标)
int dfs(int u) {
if (!son[u].size()) {
heap[++idx].push(segments[u].w);
return idx;
}
int cur = dfs(son[u][0]);
for (int i = 1; i < son[u].size(); i++) {
int p = dfs(son[u][i]);
cur = Merge(cur, p);
}
heap[cur].push(segments[u].w);
return cur;
}
int main() {
scanf("%d", &n);
segments[0] = Segment{1, 1000000, 0};
for (int i = 1; i <= n; i++) {
int l, r, w;
scanf("%d%d%d", &l, &r, &w);
segments[i] = Segment{l, r, w};
}
sort(segments, segments + n + 1);
Build();
int p = dfs(0);
LL ans = 0;
for (int i = 1; i <= n; i++) {
if (!heap[p].empty()) {
ans += heap[p].top();
heap[p].pop();
}
printf("%lld ", ans);
}
return 0;
}
¶ I Mininum Diameter Spanning Tree
题面
参考：
窝们要枚举绝对中心在哪一条边上
假设绝对中心S在边<u,v>上 离u的距离是x
根据定义 他到其他点的最短路的最大值最小 且这个最大值会出现两次
把他写成函数的形式：
做出d的图像 可以发现它是-|x|的图像平移后得到的 在区间[0,w]上的部分
而它的纵截距是d[u][i], 在直线x=w上的截距是d[v][i]
而f的图像就是这样若干个折线构成的图像的最上边
观察图像可以发现所求的f的最小值在交点处或区间端点处取得
考虑怎么求交点
把点按到u的距离降序排序的话 对答案有贡献的点到v的距离一定是升序排序的
否则那个点的d图像会被其他点的d图像压在下面
那么按到u的距离降序排个序 然后扫一遍 用lst表示上一个有贡献的i
对于当前点cur 若d[u][cur]<=d[u][lst] 且d[v][cur]<=d[v][lst] 那么cur就无用了
否则若d[v][cur]>d[v][lst] 就有d[u][cur]+x==d[v][lst]+w - x 得x == (d[v][lst]-d[u][cur]+w)/2
但窝们要求的是f的最小值 甚至可以不求出x 直接在符合条件时用d[u][cur]+d[v][lst]+w和直径比大小就行了
取得最小值 就更新一下答案
端点处用d[u][rk[u][n]] + d[v][rk[v][n]]+w更新答案
在更新答案的时候维护一下是枚举哪一条边的时候取到了这个答案
然后以这条边为起点 建出最短路径树
可以得到一颗最小直径生成树
#include<bits/stdc++.h>
using namespace std;
const int maxn = 507;
#define ll long long
const ll inf = 1ll << 61;
int n, m;
struct edge {
int u, v;
ll w;
}e[maxn * maxn];
ll d[maxn][maxn], g[maxn][maxn];
vector<int> adj[maxn];
int pre[maxn];
int rk[maxn][maxn]; //rk[i][j]表示距离点i第j近的点
ll tmp[maxn], ans, dis[maxn], X;
bool cmp(int a, int b) { return tmp[a] < tmp[b];}
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
return s * f;
}
typedef pair<int, int> pii;
set<pii, less<pii> > min_heap, res;
#define mk make_pair
void dij(int s1, int s2) {
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[s1] = X; dis[s2] = g[s1][s2] - X;
min_heap.insert(mk(dis[s1], s1));
min_heap.insert(mk(dis[s2], s2));
if (s1 != s2) {
pre[s2] = s1;
}
while(!min_heap.empty()) {
auto it = min_heap.begin();
int u = it->second;
min_heap.erase(*it);
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (dis[v] > dis[u] + g[u][v]) {
min_heap.erase(mk(dis[v], v));
dis[v] = dis[u] + g[u][v];
min_heap.insert(mk(dis[v], v));
res.erase(mk(pre[v], v));
pre[v] = u;
res.insert(mk(pre[v], v));
}
}
}
}
int main() {
n = rd(); m = rd();
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = inf;
for (int i = 1; i <= n; i++) d[i][i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, w;
u = e[i].u = rd(); v = e[i].v = rd(); w = e[i].w = g[u][v] = g[v][u] = rd()*2ll;
d[u][v] = d[v][u] = w;
adj[u].push_back(v); adj[v].push_back(u);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
rk[i][j] = j; tmp[j] = d[i][j];
}
sort(rk[i] + 1, rk[i] + n + 1, cmp);
}
ans = inf;//直径
int s1, s2;
for (int k = 1; k <= m; k++) {
int u = e[k].u, v = e[k].v;
if (d[u][rk[u][n]] == d[u][rk[u][n-1]] && d[u][rk[u][n]] * 2ll < ans) {
ans = d[u][rk[u][n]] * 2ll;//u点作为中心
s1 = s2 = u;
}
if (d[v][rk[v][n]] == d[v][rk[v][n-1]] && d[v][rk[v][n]] * 2ll < ans) {
ans = d[v][rk[v][n]] * 2ll;
s1 = s2 = v;
}
int lst, cur;
for (cur = n-1, lst = n; cur >= 1; cur--) {//d[u][i]减小 合法的d[v][i]应对应增加
if (d[v][rk[u][lst]] < d[v][rk[u][cur]]) {
if (ans > d[u][rk[u][cur]] + d[v][rk[u][lst]] + e[k].w) {
ans = d[u][rk[u][cur]] + d[v][rk[u][lst]] + e[k].w;
X = ans / 2 - d[u][rk[u][cur]];
s1 = u, s2 = v;
}
lst = cur;
}
}
}
cout << ans / 2ll << endl;
dij(s1, s2);
for (auto it = res.begin(); it != res.end(); ++it) {
printf("%d %d\n", it->first, it->second);
}
if (s1 != s2) printf("%d %d\n",s1, s2);
return 0;
}
¶ A. 6789
¶ 题意
给出一个的"扑克牌"矩阵, 其中扑克牌只有"6", "7", "8", "9".
可以旋转任意位置的扑克牌, 使扑克牌矩阵中心对称. 求最小旋转次数.
(与中心对称, 与中心对称, 只能和中心旋转后的中心对称)
¶ 题解
直接模拟即可, 判断和(中心对称位置)的牌是否可以通过旋转某一张来使得其对称. 注意中心点只有可满足条件. 详见代码.
复杂度
¶ 代码
const int maxn = 510;
int n, m, ans = 0;
char str[maxn][maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", str[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int ii = n - i + 1, jj = m - j + 1;
int a = str[i][j] - '0', b = str[ii][jj] - '0';
if (i == ii && j == jj) {
if (a != 8) {
ans = -1;
break;
}
}
else {
if (a == 6) {
if (b == 6)
ans++;
else if (b != 9) {
ans = -1;
break;
}
}
else if (a == 9) {
if (b == 9)
ans++;
else if (b != 6) {
ans = -1;
break;
}
}
else if (a == 8) {
if (b != 8) {
ans = -1;
break;
}
}
else if (a == 7) {
if (b != 7) {
ans = -1;
break;
}
else
ans++;
}
}
}
if (ans == -1)
break;
}
if (ans == -1)
puts("-1");
else
printf("%d\n", ans/2);
return 0;
}
¶ G. Lexicographically Minimum Walk
¶ 题意
给出一张个点条边的有向图, 边权为互不相等的正整数. 找一条到的路, 使得路上边权依次组成的数组字典序最小.
如果路无限长, 输出"TOO LONG"
如果不存在到的路, 输出"IMPOSSIBLE"
¶ 题解
显然贪心.
但直接贪心可能会走到某个不通向的点, 然后跑不到. 但其实可以跑其他路到.
为了避免这样的情况, 需要找一个子图, 保证子图上的每一条边都可以跑到, 在子图上贪心即可.
如何寻找这样的子图? 先建一个"反图", 从跑一遍, 记录能跑到的边, 这些边即是可以通向的边.
然后依照这些边建立一张新的图, 边依据边权排序, 然后dfs第一条边即可.
注意有环就退出.
复杂度
¶ 代码
const int maxn = 1e5+10;
const int maxm = 3e5+10;
int n, m, s, t, vis[maxn];
vector<int> G[maxm], G2[maxm], ans;
struct Edge {
int u, v, c, flag;
} edges[maxm];
bool cmp( int i, int j) {
return edges[i].c < edges[j].c;
}
void dfs(int v) {
vis[v] = 1;
for (auto i : G2[v]) {
Edge &e = edges[i];
e.flag = 1;
if (!vis[e.u])
dfs(e.u);
}
}
bool dfs2(int u) {
if (u == t)
return true;
vis[u] = 2;
Edge &e = edges[G[u][0]];
if (vis[e.v] == 2)
return false;
ans.push_back(e.c);
return dfs2(e.v);
}
void Print() {
for (auto x : ans)
printf("%d ", x);
puts("");
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
edges[i] = Edge{u, v, c, 0};
G2[v].push_back(i);
}
dfs(t);
for (int i = 1; i <= m; i++) {
Edge &e = edges[i];
if (e.flag) {
G[e.u].push_back(i);
}
}
if (!G[s].size())
puts("IMPOSSIBLE");
else {
for (int i = 1; i <= n; i++)
sort(G[i].begin(), G[i].end(), cmp);
if (dfs2(s))
Print();
else
puts("TOO LONG");
}
return 0;
}
¶ 补题期限结束后的补题
(再不学习就要被踢出校队了 
)
¶ K. Wind of Change
¶ 题意
给出两棵大小为的树, 带边权, 节点标号为1 \~ n. 对于每一个节点, 找到一个节点, 使得在两棵树中, 到的距离和最小. 求.
¶ 题解
距离先转为和有关的问题.
对两棵树点分治, 得到两棵重构的点分树. 这样一个点的最多只有个.
先形式化一下, 设分别为两棵树, 为树中的祖先到的距离.
对于每一个, 枚举其两棵树上的祖先的组合, 然后我们求两棵以为根的子树中, 共有的节点, 求出到及距离和最小的. 这样就求得了最小的. 然后再对每一个求一下
可以发现, 我们要求的和的形式是一模一样的. 所以, 我们不妨一起做: 对每个枚举两个祖先的组合, 先计算. 再找到最小值和次小值以及他们所对应的点. 如果取得最小值的点不是, 那就加上最小值; 如果是, 那就加上次小值.
的大小至少为(否则他是叶子, 叶子不可能是某个节点的祖先), 所以一定有最小值和次小值, 上述做法可行.
复杂度
具体实现:
点分是没有边权的, 只是把一棵树的结构重新构造了一下(还没做过题, 不知道重构会影响什么, 不会影响什么). 但是这里有边权, 我们重构的过程中, 甚至连边都重构了. 那么怎么办呢?
实际上, 我们不需要每一条边的权值, 所以不需要保存整棵树的结构, 需要的是, 也就是重构的树中, 节点到其祖先的距离. 找到一个重心以后, 从他开始dfs, 可以得到这棵树中每一个点到重心的距离. 而重心一定后代的祖先, 所以保存所有后代及其到重心的距离即可. 然后深搜儿子进行点分的时候, 某些后代(除了儿子以外的后代)又会新增祖先(子树的重心)及距离. 这样虽然没有保存重构树的结构 —— 根本不需要全部的结构 —— 但是保存了真正需要的东西: 祖先
仔细思考上述内容, 又可以得出结论: 重心一定是所有后代有的祖先(没有后代就不用管他). 那么我们在对第二棵树进行点分的过程中, 实际上已经在枚举了, 也就是重心. 然后, 对于的所有子代, 遍历他在中的祖先, 这样就枚举了. 可以对每一个开一个小根堆, 把压入堆中. 做完这一步, 就可以开始找最小和次小了.
重新枚举和, 先找最小, 如果就是再找次小.
由于只需要小根堆的前两个值, 所以不必用堆 —— 可以直接维护最小值和次小值, 这样就把堆的减下来了.
注意对每一个开始更新之前, 要重置"堆".
然后就做完啦啦啦!!!
¶ 代码
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
const int maxn = 2.5e5+10;
struct HeapTwo {
PLI val[2];
void Reset() {
val[0] = val[1] = make_pair(INF, -1);
}
void Push(PLI x) {
if (x < val[0])
val[1] = val[0], val[0] = x;
else if (x < val[1])
val[1] = x;
}
LL Top(int u) {
return val[u == val[0].second].first;
}
} heap[maxn];
int n, size[maxn], vis[maxn];
vector<PIL> T[2][maxn], descendant, anscentant[maxn];
LL ans[maxn];
// 维护size用来点分, 同时记录点到根的距离.
void dfs(int k, int u, int f, LL dis) {
size[u] = 1;
descendant.emplace_back(u, dis);
for (auto e : T[k][u]) {
int v = e.first;
LL w = e.second;
if (v != f && !vis[v]) {
dfs(k, v, u, dis + w);
size[u] += size[v];
}
}
}
int Center(int k, int u) {
// 每一次求重心的时候, 要重新求子代, 注意清空
descendant.clear();
dfs(k, u, 0, 0);
int tot_size = descendant.size();
for (auto des : descendant) {
int is_center = 1;
int x = des.first;
for (auto e : T[k][x]) {
int v = e.first;
if (vis[v])
continue;
// size[x] > size[v] == v 是 x 的儿子
if (size[x] > size[v] && (size[v] << 1) > tot_size) {
is_center = 0;
break;
}
// size[x] < size[v] == v 是 x 的父亲
if (size[x] < size[v] && ((tot_size - size[x]) << 1) > tot_size) {
is_center = 0;
break;
}
}
if (is_center) {
// 找到重心, 需要以重心为根, 求一下子代到根(这个祖先)的距离
descendant.clear();
dfs(k, x, 0, 0);
return x;
}
}
return -1;
}
void Decomp0(int k, int u) {
int c = Center(k, u);
for (auto des : descendant)
// c 为所有子代的一个祖先
anscentant[des.first].emplace_back(c, des.second);
// 删除c, 做剩下的森林
vis[c] = 1;
for (auto e : T[k][c]) {
int v = e.first;
if (!vis[v])
Decomp0(k, v);
}
// 深搜, 可回溯, 节省空间(虽然不是很必要)
vis[c] = 0;
}
void Decomp1(int k, int u) {
int c = Center(k, u);
// 先初始化堆
for (auto des : descendant) {
int v = des.first;
for (auto ansc : anscentant[v]) {
int a1 = ansc.first;
heap[a1].Reset();
}
}
// 对所有(L1, L2), 把所有 dist(T1, c, v) + dist(T2, a, v) 压入堆
// 得到每个(L1, L2)的最小值和次小值
for (auto des : descendant) {
int v = des.first;
LL dis2 = des.second;
for (auto ansc : anscentant[v]) {
int a1 = ansc.first;
LL dis1 = ansc.second;
heap[a1].Push(make_pair(dis1 + dis2, v));
}
}
// 更新答案
for (auto des : descendant) {
int v = des.first;
LL dis1 = des.second;
for (auto ansc : anscentant[v]) {
int a1 = ansc.first;
LL dis2 = ansc.second;
ans[v] = min(ans[v], dis1 + dis2 + heap[a1].Top(v));
}
}
// 继续点分
vis[c] = 1;
for (auto e : T[k][c]) {
int v = e.first;
if (!vis[v])
Decomp1(k, v);
}
vis[c] = 0;
}
int main() {
scanf("%d", &n);
for (int k = 0; k < 2; k++)
for (int i = 1; i < n; i++) {
int u, v;
LL w;
scanf("%d%d%lld", &u, &v, &w);
T[k][u].emplace_back(v, w);
T[k][v].emplace_back(u, w);
}
Decomp0(0, 1);
for (int i = 1; i <= n; i++)
ans[i] = INF;
Decomp1(1, 1);
for (int i = 1; i <= n; i++)
printf("%lld\n", ans[i]);
return 0;
}