opencup-gym102391
J RQD-IGVA树 树上DSU
最开始以为险段长度跟n无关，所以加了根[1, n]的线段进去就WA到死，后来改成[1, 1000000]即可。
大概是叫dsu on tree，可以处理一些与子树有关的询问，复杂度Onlogn
可惜IGVA不知道场上什么地方写挫了 场后10分钟A了
1const int maxn = 3e5 + 10;
2
3int n, w[maxn];
4struct star{int to, next;};
5int head[maxn], top = 0;
6star edge[maxn];
7void add(int u, int v){
8 edge[top].to = v;
9 edge[top].next = head[u];
10 head[u] = top++;
11}
12
13struct NODE{
14 int l, r, w;
15 bool operator < (const NODE &b) const{
16 if(l != b.l) return l < b.l;
17 else return r > b.r;
18 }
19};
20vector<NODE> vec;
21priority_queue<ll> pq[maxn];
22int conv[maxn];
23vector<ll> temp;
24
25//合并边i和边j的优先队列，放到i里面
26void merge(int i , int j){
27 temp.clear();
28 if(pq[conv[i]].size() < pq[conv[j]].size()) swap(conv[i], conv[j]);
29
30 while(!pq[conv[j]].empty()){
31 temp.push_back(pq[conv[i]].top() + pq[conv[j]].top());
32 pq[conv[i]].pop(); pq[conv[j]].pop();
33 }
34 for(auto x: temp) pq[conv[i]].push(x);
35}
36
37void sove(int now){
38 for(int i = head[now]; ~i; i = edge[i].next){
39 sove(edge[i].to);
40 merge(now, edge[i].to);
41 }
42 pq[conv[now]].push(vec[now].w);
43}
44
45stack<int> sta;
46
47int main(){
48 // Fastin;
49 clr(head, -1);
50 scanf("%d", &n);
51 for(int i = 1; i <= n; i++){
52 int u, v, w; scanf("%d %d %d", &u, &v, &w);
53 vec.push_back({u, v, w});
54 }
55 vec.push_back({1, 1000000, 0});
56 sort(vec.begin(), vec.end());
57
58 sta.push(0);
59 for(int i = 1; i <= n; i++){
60 int top = sta.top();
61 while(!(vec[top].l <= vec[i].l && vec[i].r <= vec[top].r)){
62 sta.pop();
63 if(sta.empty()){while(1);};
64 top = sta.top();
65 }
66 add(top, i); sta.push(i);
67 }
68
69 for(itn i = 0; i <= n; i++) conv[i] = i;
70 sove(0);
71
72 ll ans = 0;
73 for(int i = 1; i <= n; i++){
74 if(!pq[conv[0]].empty()){
75 ans += pq[conv[0]].top(); pq[conv[0]].pop();
76 }
77 printf("%lld ", ans);
78 }
79
80 return 0;
81}I 最小直径生成树 MDST
为了求解MDST，就需要求解绝对中心所在的位置。绝对中心不一定在节点上，可以在边上。
当选定某条边<u, v>后，min(某点到u的距离，某点到v的距离)是一个单峰函数^，把所有的点的山峰函数放到一张图中，那么应该从最顶端的折线中找一个最低点。因为会出现山峰完全被另一个山峰嵌套的情况，所以将所有点按照到u的距离排升序，有意义的折点一定是被那些到v距离呈降序的点。以此就可不断遍历上述折线，找到绝对中心所在的边。
找到生成树的绝对中心后，即可dijstra或其他什么办法找到最短路径生成树。通过数学计算，可以知道中心在距离u点$ans - 2 * dis[i][rk[i][now]]$的位置，很快的可以知道距离v点的距离。那么以绝对中心为起点跑dijstra，就等价于将u点和v点更新为中心到其的距离，其余设置为inf。为了避免除以2的浮点数出现，将所有的权值扩大为2倍即可。
1const int maxn = 5e2 + 10;
2const ll inf = 1ll << 60;
3int n, m;
4ll a[maxn][manx], dis[maxn][maxn];
5int rk[maxn][maxn];
6
7ll ans; int ansi, ansj;
8
9struct NODE{
10 int to; ll d;
11 bool operator < (const NODE &b) const{
12 return d > b.d;
13 }
14};
15priority_queue<NODE> pq;
16ll D[maxn], dx; int par[maxn];
17void getpath(){
18 D[ansi] = dx; pq.push({ansi, D[ansi]});
19 if(ansi != ansj){
20 D[ansj] = 2 * a[ansi][ansj] - dx; pq.push({ansj, D[ansj]}); par[ansj] = ansi;
21 }
22 while(!pq.empty()){
23 NODE temp = pq.top(); pq.pop();
24 int to = temp.to; ll d = temp.d;
25 if(d > D[to]) continue;
26 for(int i = 1; i <= n; i++) if(D[i] > d + 2 * a[to][i]){
27 D[i] = d + 2 * a[to][i];
28 par[i] = to;
29 pq.push({i, D[i]});
30 }
31 }
32}
33
34int main(){
35 // Fastin;
36 scanf("%d%d", &n, &m);
37 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = dis[i][j] = inf;
38 for(int i = 1; i <= n; i++) dis[i][i] = 0;
39 for(int i = 1; i <= m; i++){
40 int u, v, w; scanf("%d %d %d", &u, &v, &w);
41 a[u][v] = a[v][u] = w;
42 dis[u][v] = dis[v][u] = min(dis[u][v], 1ll * w);
43 }
44 for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j)
45 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
46 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) rk[i][j] = j;
47 for(int i = 1; i <= n; i++) sort(rk[i] + 1, rk[i] + 1 + n, [i](int a, int b)->bool{return dis[i][a] < dis[i][b];});
48 ans = inf;
49 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j && a[i][j] != inf){
50 update(dis[i][rk[i][n]] * 2, i, i);
51 update(dis[j][rk[j][n]] * 2, j, j);
52 int pre = n;
53 for(int now = n - 1; now >= 1; now--){
54 if(dis[j][rk[i][now]] > dis[j][rk[i][pre]]){
55 ll temp = dis[j][rk[i][pre]] + dis[i][rk[i][now]] + a[i][j];
56 if(temp < ans){
57 ans = tmep;
58 ansi = i; ansj = j;
59 dx = ans - 2 * dis[i][rk[i][now]];
60 }
61 pre = now;
62 }
63 }
64 }
65 printf("%lld\n", ans);
66 for(int i = 1; i <= n; i++) D[i] = inf;
67 getpath();
68 for(int i = 1; i <= n; i++) if(par[i]) printf("%d %d\n", i, par[i], a[i][par[i]]);
69 return 0;
70}