树上的路径 BZOJ 3784

时间:2021-08-14 09:45:58

树上的路径

【问题描述】

给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序,输出前M个距离值。

【输入格式】

第一行两个正整数N,M
下面N-1行,每行三个正整数a,b,c(a,b<=N,C<=10000)。表示结点a到结点b有一条权值为c的边。
【输出格式】
共M行,如题所述.

【样例输入】

5 10
1 2 1
1 3 2
2 4 3
2 5 4

【样例输出】

7
7
6
5
4
4
3
3
2
1
【数据范围】

N<=50000,M<=Min(300000,n*(n-1) /2 )


题解:

考虑将点分治时访问的点的顺序作为一个序列

每个位置都有其对应的区间(指向这个位置所在重心树访问的前面所有子树,那么这就代表了这个位置对应的点出发经过这个重心的所有路径)

那么原问题转化为了BZOJ 2006 超级钢琴的问题

  1 #include<cmath>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 const int inf = 2147483647;
 10 const int logn = 16;
 11 const int logs = 20;
 12 const int maxn = 5e4 + 1;
 13 const int maxm = maxn << 1;
 14 const int maxs = maxn * logn + 1;
 15 inline void Scan(int &x)
 16 {
 17     char c;
 18     bool o = false;
 19     while(!isdigit(c = getchar())) o = (c != '-') ? o : true;
 20     x = c - '0';
 21     while(isdigit(c = getchar())) x = x * 10 + c - '0';
 22     if(o) x = -x;
 23 }
 24 int tot, nex[maxm], ver[maxm], fir[maxn], val[maxm];
 25 inline void Ins(int x, int y, int z)
 26 {
 27     nex[++tot] = fir[x];
 28     fir[x] = tot;
 29     ver[tot] = y;
 30     val[tot] = z;
 31 }
 32 int sum, root;
 33 int size[maxn], heavy[maxn];
 34 bool vis[maxn];
 35 void Getroot(int u, int f)
 36 {
 37     heavy[u] = 0;
 38     size[u] = 1;
 39     for(int i = fir[u]; i; i = nex[i])
 40     {
 41         int v = ver[i];
 42         if(v == f || vis[v]) continue;
 43         Getroot(v, u);
 44         size[u] += size[v];
 45         heavy[u] = max(heavy[u], size[v]);
 46     }
 47     heavy[u] = max(heavy[u], sum - size[u]);
 48     if(heavy[u] < heavy[root]) root = u;
 49 }
 50 struct couple
 51 {
 52     int l, r;
 53 };
 54 couple c[maxs];
 55 int num, l, r;
 56 int dis[maxn], len[maxs];
 57 int big[logs][maxs];
 58 void Getdis(int u, int f)
 59 {
 60     len[++num] = dis[u], big[0][num] = num;
 61     c[num] = (couple) {l, r};
 62     for(int i = fir[u]; i; i = nex[i])
 63     {
 64         int v = ver[i];
 65         if(v == f || vis[v]) continue;
 66         dis[v] = dis[u] + val[i];
 67         Getdis(v, u);
 68     }
 69 }
 70 void Div(int u)
 71 {
 72     root = 0;
 73     Getroot(u, 0);
 74     l = r = ++num;
 75     len[num] = 0, big[0][num] = num;
 76     vis[root] = true;
 77     for(int i = fir[root]; i; i = nex[i])
 78     {
 79         int v = ver[i];
 80         if(vis[v]) continue;
 81         dis[v] = val[i];
 82         Getdis(v, root);
 83         r = num;
 84     }
 85     for(int i = fir[root]; i; i = nex[i])
 86     {
 87         int v = ver[i];
 88         if(vis[v]) continue;
 89         sum = size[v];
 90         Div(v);
 91     }
 92 }
 93 inline int Max(int a, int b)
 94 {
 95     return (len[a] > len[b]) ? a : b;
 96 }
 97 int bin[logs], lg[maxs];
 98 inline void Rmq()
 99 {
100     int lgn = log2(num);
101     bin[0] = 1;
102     for(int i = 1; i <= lgn; ++i) bin[i] = bin[i - 1] << 1, lg[bin[i]] = 1;
103     for(int i = 1; i <= num; ++i) lg[i] += lg[i - 1];
104     for(int k = 1; k <= lgn; ++k)
105         for(int i = 1; i <= num; ++i)
106         {
107             if(i + bin[k] - 1 > num) continue;
108             int j = i + bin[k - 1];
109             big[k][i] = Max(big[k - 1][i], big[k - 1][j]);
110         }
111 }
112 inline int Query(int l, int r)
113 {
114     if(l > r) return -1;
115     int len = lg[r - l + 1];
116     return Max(big[len][l], big[len][r - bin[len] + 1]);
117 }
118 int n, m;
119 struct interval
120 {
121     int l, r, a, b, v;
122 };
123 inline bool operator < (interval a, interval b)
124 {
125     return a.v < b.v;
126 }
127 priority_queue <interval> q;
128 int main()
129 {
130     Scan(n), Scan(m);
131     int a, b;
132     for(int i = 1; i < n; ++i)
133     {
134         int c;
135         Scan(a), Scan(b), Scan(c);
136         Ins(a, b, c), Ins(b, a, c);
137     }
138     sum = n;
139     root = 0;
140     heavy[0] = inf;
141     Div(1);
142     Rmq();
143     int x;
144     for(int i = 1; i <= num; ++i)
145     {
146         a = c[i].l, b = c[i].r;
147         if(a)
148         {
149             x = Query(a, b);
150             q.push((interval) {a, b, i, x, len[i] + len[x]});
151         }
152     }
153     int u, v;
154     interval s;
155     while(m--)
156     {
157         s = q.top(), q.pop();
158         u = Query(s.l, s.b - 1);
159         v = Query(s.b + 1, s.r);
160         if(u > 0) q.push((interval) {s.l, s.b - 1, s.a, u, len[u] + len[s.a]});
161         if(v > 0) q.push((interval) {s.b + 1, s.r, s.a, v, len[v] + len[s.a]});
162         printf("%d\n", s.v);
163     }
164 }