J RQD-IGVA树 树上DSU 最开始以为险段长度跟n无关，所以加了根[1, n]的线段进去就WA到死，后来改成[1, 1000000]即可。
大概是叫dsu on tree，可以处理一些与子树有关的询问，复杂度Onlogn
可惜IGVA不知道场上什么地方写挫了 场后10分钟A了
cpp 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，就需要求解绝对中心所在的位置。绝对中心不一定在节点上，可以在边上。
...
ACM
树
构造
1094字
C 思维 & 树 C* Namomo 2C 区间减1，代价为长度的平方，问将区间操作为全0的最小代价和最大代价。
cpp 1#include <iostream> 2 3#include <algorithm> 4#include <string> 5#include <vector> 6#include <stack> 7#include <queue> 8#include <set> 9#include <map> 10#include <unordered_map> 11#include <unordered_set> 12#include <random> 13#include <chrono> 14 15#include <cstdio> 16#include <cstring> 17#include <cmath> 18#include <ctime> 19#include <cstdlib> 20#include <cassert> 21 22#define itn int 23#define fro for 24#define scnaf scanf 25#define sacnf scanf 26#define Fastin freopen("in.txt", "r", stdin) 27#define Fastout freopen("out.txt", "w", stdout) 28#define manx maxn 29#define lowbit(x) ((x) & (-x)) 30#define ceil(n, p) (((n) +(p) - 1) / (p)) 31#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n') 32#define clr(a, x) memset((a), x, sizeof (a)) 33#define min(a, b) ((a) < (b)? (a): (b)) 34#define max(a, b) ((a) > (b)? (a): (b)) 35 36using namespace std; 37typedef long long ll; 38 39int read(){ 40 int ng=0,x=0; 41 char ch=getchar(); 42 for(;ch<'0' || ch>'9';ch=getchar()) ng|=ch=='-'; 43 for(;ch>='0' && ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; 44 return ng?-x:x; 45} 46/*------------------------------------------------------------------------------------*/ 47ll gcd(ll x, ll y){return !x? y: gcd(y % x, x);} 48void exgcd(ll a, ll b, ll &x, ll &y){ 49 if(!b){x = 1; y = 0;return;} 50 exgcd(b, a % b, y, x); y -= a / b * x; 51} 52ll qp(ll a, ll p){ 53 if(p < 0) return 0; 54 ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;} 55 return ans; 56} 57ll qp(ll a, ll p, ll M){ 58 ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;} 59 return ans; 60} 61/*------------------------------------------------------------------------------------*/ 62 63const int maxn = 5e5 + 10; 64const int M = 1e9 + 7; 65int a[maxn], b[maxn]; 66 67ll cal(int l, int r){return (r - l) * 1ll * (r - l) % M;} 68 69stack<pair<int, int>> sta; 70 71int main(){ 72// Fastin; 73 int n; scnaf("%d", &n); 74 for(int i = 1; i <= n; i++) scanf("%d", a + i); a[n + 1] = 0; 75 76 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 77 while(b[n + 1] == 0) n--; 78 ll ans = 0; 79 int p = 1, q = 1; while(b[q] >= 0) q++; 80 while(p <= n + 1){ 81 if(b[p] + b[q] > 0){ 82 ans += -b[q] * cal(p, q); ans %= M; 83 b[p] += b[q]; 84 q++; while(q <= n + 1 && b[q] >= 0) q++; 85 } 86 else if(b[p] + b[q] == 0){ 87 ans += b[p] * cal(p, q); ans %= M; 88 p++; q++; while(p <= n + 1 && b[p] < 0) p++; while(q <= n + 1 && b[q] >= 0) q++; 89 } 90 else{ 91 ans += b[p] * cal(p, q); ans %= M; 92 b[q] += b[p]; 93 p++; while(p <= n + 1 && b[p] < 0) p++; 94 95 } 96 } 97 printf("%lld ", ans % M); 98 99 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 100 ans = 0; 101 for(int i = 1; i <= n + 1; i++){ 102 if(b[i] > 0) sta.push({i, b[i]}); 103 else if(b[i] < 0){ 104 while(1){ 105 pair<int, int> now = sta.top(); sta.pop(); 106 if(now.second + b[i] < 0){ 107 ans += now.second * cal(now.first, i); ans %= M; 108 b[i] += now.second; 109 } 110 else{ 111 ans += -b[i] * cal(now.first, i); ans %= M; 112 now.second += b[i]; 113 sta.push(now); 114 break; 115 } 116 117 } 118 } 119 } 120 121 printf("%lld\n", ans); 122 123 return 0; 124} I 构造 虽然感觉还是说不太清楚qaq
...