1: 整数删除
思路：题目给定数据范围 $5e5$，考虑 $O(nlogn)$ 的做法，每次挑一个最小数的删除，如果出现相同数则删除靠前的，并将其值贡献给相邻单位，可见可以使用 $pair<int,int>$ 型小根堆来维护最小的值，并模拟赋值过程，用数组模拟前后链表，每删除一个数将被删的数前后两端用链表连通即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int pre[N];
int suf[N];
int a[N];
signed main(){
int n, k;
cin >> n >> k;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
for(int i = 1; i <= n; i ++){
cin >> a[i];
pre[i] = i - 1;
suf[i] = i + 1;
heap.push({a[i], i});
}
while(k --){
while(a[heap.top().second] != heap.top().first){
heap.pop();
}
pair<int,int> now = heap.top();
heap.pop();
int val = now.first;
int id = now.second;
int pr = pre[id];
int su = suf[id];
pre[id] = -1;
suf[id] = -1;
if(pr != 0){
a[pr] += val;
heap.push({a[pr], pr});
}
if(su != n + 1){
a[su] += val;
heap.push({a[su], su});
}
if(su == n + 1){
suf[pr] = n + 1;
}else if(pr == 0){
pre[su] = 0;
}else{
suf[pr] = su;
pre[su] = pr;
}
}
int start = -1;
for(int i = 1; i <= n; i ++){
if(pre[i] == 0){
start = i;
break;
}
}
for(int i = start; i != n + 1; i = suf[i]){
cout << a[i] <<' ';
}
cout << endl;
return 0;
}
2: 景区导游
思路：手玩一下样例可以看出如果所有景点都经过，那么总代价就是 $1 - n$ 中任意相邻景点的 $LCA$ 距离 之和，而跳过景点无疑是总代价减去该景点与其上一景点和该景点与其下一景点的 $LCA$距离 ，并加上上一景点到下一景点的 $LCA$ 距离, 比如 $3 - 6 - 4$ 游玩顺序，如果跳过游玩 $6$ ，那么代价更新就是总代价 $-= LCA(3, 6) + LCA(6, 4) + LCA(3, 4)$。而 $LCA(a,b)$ 的距离可以通过根到 $a$ 的距离 + 根到 $b$ 的距离 - $2$ * 根到 $LCA(a, b)$ 的距离获得。
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int path[N];
int h[N], e[N], ne[N], idx, w[N];
int dep[N];
int fa[N][25];
int dist[N];
int ans;
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
void bfs(int root){
memset(dep, 0x3f, sizeof dep);
dep[root] = 1;
dep[0] = 0;
queue<int> q;
q.push(root);
while(q.size()){
auto x = q.front();
q.pop();
for(int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if(dep[j] > dep[x] + 1){
dist[j] = dist[x] + w[i];
dep[j] = dep[x] + 1;
q.push(j);
fa[j][0] = x;
for(int k = 1; k <= 20; k ++){
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int k = 20; k >= 0; k --){
if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
}
if(a == b) return a;
for(int k = 20; k >= 0; k --){
if(fa[a][k] != fa[b][k]){
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
signed main(){
memset(h, -1, sizeof h);
memset(dist, 0x3f,sizeof dist);
int n, k;
cin >> n >> k;
for(int i = 1; i <= n - 1; i ++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
for(int i = 1; i <= k; i ++){
cin >> path[i];
}
dist[path[1]] = 0;
bfs(path[1]);
for(int i = 2; i <= k; i ++){
ans += dist[path[i]] + dist[path[i - 1]] - 2 * dist[lca(path[i] , path[i - 1])];
}
for(int i = 1; i <= k; i ++){
if(i == 1){
ans -= dist[path[1]] + dist[path[2]] - 2 * dist[lca(path[1], path[2])];
cout << ans << ' ';
ans += dist[path[1]] + dist[path[2]] - 2 * dist[lca(path[1], path[2])];
}else if(i == k){
ans -= dist[path[k - 1]] + dist[path[k]] - 2 * dist[lca(path[k - 1], path[k])];
cout << ans << ' ';
ans += dist[path[k - 1]] + dist[path[k]] - 2 * dist[lca(path[k - 1], path[k])];
}else{
ans -= dist[path[i - 1]] + dist[path[i]] - 2 * dist[lca(path[i - 1], path[i])];
ans -= dist[path[i + 1]] + dist[path[i]] - 2 * dist[lca(path[i + 1], path[i])];
ans += dist[path[i - 1]] + dist[path[i + 1]] - 2 * dist[lca(path[i + 1], path[i - 1])];
cout << ans << ' ';
ans += dist[path[i - 1]] + dist[path[i]] - 2 * dist[lca(path[i - 1], path[i])];
ans += dist[path[i + 1]] + dist[path[i]] - 2 * dist[lca(path[i + 1], path[i])];
ans -= dist[path[i - 1]] + dist[path[i + 1]] - 2 * dist[lca(path[i + 1], path[i - 1])];
}
}
return 0;
}
3: 砍树
思路：同样手玩一下样例可以看出最终所要的结果一定是从所有 $m$ 个组合中 $LCA$ 路径覆盖的边中出现过 $m$ 次的边中选，因为只有这些边被砍才会出现任意 $a$ 和 $b$ 不连通，求边覆盖次数用 $LCA$ + 树上边差分即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int e[N], ne[N], h[N];
int dep[N];
int fa[N][25];
int a[N];
int idx;
int s[N];
pair<int,int> edge[N];
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void bfs(int root){
memset(dep, 0x3f, sizeof dep);
dep[0] = 0;
dep[root] = 1;
queue<int> q;
q.push(root);
while(q.size()){
auto x = q.front();
q.pop();
for(int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if(dep[x] + 1 < dep[j]){
dep[j] = dep[x] + 1;
q.push(j);
fa[j][0] = x;
for(int k = 1; k <= 20; k ++){
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int k = 20; k >= 0; k --){
if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
}
if(a == b) return a;
for(int k = 20; k >= 0; k --){
if(fa[a][k] != fa[b][k]){
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
void dfs(int u, int fa){
s[u] = a[u];
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa)continue;
dfs(j, u);
s[u] += s[j];
}
}
signed main(){
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; i ++){
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
edge[i] = {a,b};
}
int ans = -1;
bfs(1);
for(int i = 1; i <= m; i ++){
int x, y;
cin >> x >> y;
a[x] ++;
a[y] ++;
a[lca(x, y)] -= 2;
}
dfs(1, -1);
for(int i = n - 1; i >= 1; i --){
int x = edge[i].first;
int y = edge[i].second;
if(dep[x] < dep[y]) swap(x, y);
if(s[x] == m){
ans = i;
break;
}
}
cout << ans << endl;
return 0;
}
