fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using pii = pair<int, int>;
  7. const int N = 150005;
  8. int n, m, ans = 0;
  9. vector<int> G[N];
  10. struct Node {
  11.     int s, t, p;
  12. };
  13. Node a[N];
  14.  
  15. namespace sub1 {
  16. vector<int> Gr[N];
  17. int cnt[N], sum = 0;
  18. void dfs(int u, int pre) {
  19.     for (int i: Gr[u]) {
  20.         cnt[i]++;
  21.         if (cnt[i] == 2) sum += a[i].p;
  22.     }
  23.     ans = max(ans, sum);
  24.     for (int v: G[u]) if (v != pre) {
  25.         dfs(v, u);
  26.     }
  27.     for (int i: Gr[u]) {
  28.         if (cnt[i] == 2) sum -= a[i].p;
  29.         cnt[i]--;
  30.     }
  31. }
  32. void solve() {
  33.     sum = 0;
  34.     fill(cnt + 1, cnt + m + 1, 0);
  35.     for (int i = 1; i <= m; i++) {
  36.         Gr[a[i].s].push_back(i);
  37.         Gr[a[i].t].push_back(i);
  38.     }
  39.     for (int i = 1; i <= n; i++) if (G[i].size() == 1) dfs(i, i);
  40.     cout << ans << '\n';
  41.     for (int i = 1; i <= n; i++) Gr[i].clear();
  42. }
  43. };
  44. /*
  45. sub 1:
  46. Chọn mỗi đỉnh làm gốc và DFS:
  47. Trong quá trình dfs sẽ lưu cnt[i] là số đỉnh của cặp truyền thông i xuất hiện trong đoạn từ root -> u
  48. nếu cnt[i] == 2 thì sum += p
  49. time complexity: O(N * (N + M))
  50. */
  51. const int LG = 18;
  52. int tin[N], tout[N], stt;
  53. int h[N], up[N][LG];
  54. struct square {
  55.     int x1, x2, y1, y2, p;
  56. };
  57. vector<square> SQ;
  58. void dfsInit(int u) {
  59. }
  60. inline bool insideTreeU(int u, int v) {
  61.  
  62. }
  63. int jump(int u, int k){
  64. }
  65. int getDircetChildU(int u, int v) {
  66.  
  67. }
  68. void init() {
  69.  
  70. }
  71.  
  72. namespace sub2 {
  73. int ps[1005][1005];
  74. void solve() {
  75.     init();
  76.     for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= n + 1; j++) ps[i][j] = 0;
  77.     for (square sq: SQ) if (sq.x1 <= sq.x2 && sq.y1 <= sq.y2) {
  78.         ps[sq.x1][sq.y1] += sq.p;
  79.         ps[sq.x1][sq.y2 + 1] -= sq.p;
  80.         ps[sq.x2 + 1][sq.y1] -= sq.p;
  81.         ps[sq.x2 + 1][sq.y2 + 1] += sq.p;
  82.     }
  83.     for (int i = 1; i <= n; i++) {
  84.         for (int j = 1; j <= n; j++) {
  85.             ps[i][j] = ps[i][j] + ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
  86.             ans = max(ans, ps[i][j]);
  87.         }
  88.     }
  89.     cout << ans << "\n";
  90. }
  91. };
  92. /*
  93. *Lưu ý, solve đang viết cho trường hợp cặp truyền thông s và t khác nhau, (vì code mẫu nó thế =))), còn s == t thì chịu =))))
  94.  
  95. sub 2:
  96. Dfs trải phẳng cây bằng Euler tour với gốc từ 1, lưu tin và tout
  97. Xét cặp truyền thông s và t (đổi chỗ s, t để tin[s] <= tin[t] cho dễ xẻt):
  98. *Các cặp đỉnh (x, y) (để x <= y cho dễ xét) sẽ thỏa mãn cặp truyền thông (s, t) khi cả đỉnh s và t nằm trên đường đi từ x->y
  99. *Ngoài ra, những cặp đỉnh (x,y) thỏa mãn (s, t) đó sẽ tạo thành một/hai vùng chữ nhật như sau:
  100. + Case 1: s và t ở 2 nhánh khác nhau (s không phải là tổ tiên của t)
  101. Khi đó x nằm trong cây con của s và y nằm trong cây con của t sẽ luôn thỏa mãn
  102. ⇒ Tạo ra hình chữ nhật: [tin[s], tout[s]] x [tin[t], tout[t]] với trọng số p
  103. Xem hình ở đây cho dễ hiểu: https://f...content-available-to-author-only...e.host/i/K0Bj8zb
  104.  
  105. + Case 2: s là tổ tiên của t
  106. Gọi u là đứa con của s nằm trên đường s -> t. (dễ dàng tìm bằng binary lifting trong O(logN))
  107. Muốn đường (x, y) chứa cả s và t thì một đầu mút phải ở trong cây con của t, còn đầu kia phải nằm ngoài cây con của u
  108. (vì nếu đều ở trong thì đường không "chạm" tới s).
  109. Do ta xét cặp x, y và đặt trục tung theo y là cây con của t, phần theo trục hoành là "ngoài cây con u" tách thành hai đoạn:
  110.  
  111. [1, tin[u]-1] và [tout[u]+1, N]
  112. ⇒ Tạo ra hai hình chữ nhật: [1, tin[u]-1] x [tin[t], tout[t]], [tout[u]+1,N] x [tin[t], tout[t]] với trọng số p.
  113. Xem hình ở đây cho dễ hiểu: https://f...content-available-to-author-only...e.host/i/graph1758850484785.K0BVzMB
  114.  
  115. Ngoài ra do đã cố định x <= y, nên khi cài ta cũng cần đảo lại (hay push thêm) cặp(y, x);
  116.  
  117. Giờ đây chuyển sang bài toán:
  118. Cho hình vuông N x N:
  119. Cập nhập [x1->x2] x [y1->y2] lên p giá tị
  120.  
  121. Tìm max (x, y)
  122.  
  123. Với sub 2 N = 1e4
  124. Ta có thể fill bằng prefix sum (tuy nhiên nếu vậy sẽ tốn bộ nhớ N * N).
  125. Ngoài ra còn có thể cài sweepline nhưng update O (N)
  126. time complexity: O(N * N + MlogN + NlogN)
  127.  
  128. Hoặc cài chia căn:
  129. (n+m)n
  130. time complexity: O((N + M)√(N) + MlogN + NlogN)
  131.  
  132. (Do lười nên code sẽ code dạng prefix sum fill đoạn)
  133. */
  134.  
  135. namespace sub3 {
  136. int st[N * 4], lz[N * 4];
  137. struct Edge {
  138.     int x1, x2, y, p;
  139. };
  140. vector<Edge> E;
  141. void build(int id, int l, int r) {
  142.  
  143. }
  144. void down(int id) {
  145.  
  146. }
  147. void update(int id, int l, int r, int u, int v, int t) {
  148.  
  149. }
  150. void solve() {
  151.     init();
  152.  
  153.     cout << ans << "\n";
  154. }
  155. };
  156.  
  157. /*
  158. sub 3:
  159. Với N = 150000
  160. Ta cập nhập bằng Duyệt quét (sweep-line) theo y + Cây đoạn (segment tree) 1D trên x
  161. Mỗi hình chữ nhật [X1, X2] × [Y1, Y2] được tách thành hai sự kiện:
  162. Mở tại y = Y₁: cộng +p cho khoảng x ∈ [X1, X2].
  163. Đóng tại y = Y2 + 1: cộng -p cho khoảng x ∈ [x1, X2].
  164. segtree lazy range add trực tiếp trên mảng giá trị A (A[x] = tổng trọng số đang phủ tại hoành độ x).
  165. Mỗi sự kiện [x1,x2] là range add A[x1..x2]+=w; sau khi xử lý tất cả sự kiện của một y, lấy max(A)
  166. Sau khi xử lý các sự kiện của y, cập nhật res = max(res, tree[1].max).
  167. Kết luận: res chính là tổng lợi nhuận lớn nhất khi chọn một đường trên cây.
  168. time complexity: O((N + M)logN)
  169.  
  170. *Ngoài ra có thể cài BIT2D nhưng không nên
  171. */
  172. signed main() {
  173.     cin.tie(NULL)->sync_with_stdio(false);
  174.     if(ifstream("NETSRV.inp")) {
  175.         freopen("NETSRV.inp", "r", stdin);
  176.         freopen("NETSRV.out", "w", stdout);
  177.     }
  178.     int tt; cin >> tt;
  179.     while(tt--) {
  180.         cin >> n;
  181.         for (int i = 1; i < n; i++) {
  182.             int u, v; cin >> u >> v;
  183.             G[u].push_back(v);
  184.             G[v].push_back(u);
  185.         }
  186.         cin >> m;
  187.         for (int i = 1; i <= m; i++) {
  188.             cin >> a[i].s >> a[i].t >> a[i].p;
  189.         }
  190.         // sub3::solve();
  191.         if (n <= 100) sub1::solve();
  192.         else if (n <= 1000) sub2::solve();
  193.         else sub3::solve();
  194.  
  195.         for (int i = 1; i <= n; i++) G[i].clear();
  196.         ans = 0; 
  197.     }
  198.     return 0;
  199. }
Success #stdin #stdout 0.01s 14364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YG27N7
https://f...content-available-to-author-only...e.host/i/K0Bj8zb
https://f...content-available-to-author-only...e.host/i/graph1758850484785.K0BVzMB
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!