Snapper_001

Untitled

Mar 19th, 2023
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.87 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  5. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
  6. #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef vector<vi> vvi;
  10. typedef pair<int,int> pi;
  11. const int mxN = 1e5+1, oo = 1e9;
  12. /*
  13. 4
  14. 1 2
  15. 2 3
  16. 2 4
  17. 4
  18. 1 4 5
  19. 1 2 3
  20. 2 3 2
  21. 3 4 1
  22.  
  23. */
  24. int main() {
  25. int n; cin >> n;
  26. vvi adj(n);
  27. for(int i=0;i<n-1;++i) {
  28. int u,v; cin >> u >> v;
  29. --u,--v;
  30. adj[u].push_back(v);
  31. adj[v].push_back(u);
  32. }
  33. int q; cin >> q;
  34. vector<set<pi>> s(n);
  35. while(q--) {
  36. int u,v,w; cin >> u >> v >> w;
  37. --u,--v;
  38. s[u].insert({w,q});
  39. s[v].insert({w,q});
  40. }
  41.  
  42. vi best(n,oo);
  43. auto dfs = [&](auto&& self, int at, int from) -> void {
  44. auto& b = best[at];
  45. for(int to : adj[at]) if(to!=from) {
  46. self(self,to,at);
  47. if(s[to].size()>s[at].size()) swap(s[at],s[to]); // small to large
  48. for(auto [w,id] : s[to]) {
  49. b=min(b,w); // this is done to ensure the LCA itself also
  50. if(s[at].count({w,id})) {
  51. s[at].erase({w,id}); // found the LCA of a path query, so delete this from the set.
  52. } else s[at].insert({w,id});
  53. }
  54. s[to].clear();
  55. }
  56. if(!s[at].empty()) b=min(b,s[at].begin()->first);
  57. };
  58. dfs(dfs,0,0);
  59. for(auto i : best) cout << i << '\n';
  60. }
Advertisement
Add Comment
Please, Sign In to add comment