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，就需要求解绝对中心所在的位置。绝对中心不一定在节点上，可以在边上。
...