Snapper_001

Untitled

Mar 19th, 2023
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.92 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. int main() {
  14. int n; cin >> n;
  15. vvi adj(n);
  16. for(int i=0;i<n-1;++i) {
  17. int u,v; cin >> u >> v;
  18. --u,--v;
  19. adj[u].push_back(v);
  20. adj[v].push_back(u);
  21. }
  22. int q; cin >> q;
  23. vector<set<pi>> s(n);
  24. while(q--){
  25. int u,v,w; cin >> u >> v >> w;
  26. --u,--v;
  27. s[u].insert({w,q});
  28. s[v].insert({w,q});
  29. }
  30.  
  31. vi best(n,oo);
  32. function<void(ll, ll)> dfs = [&](int root, int parent){
  33. auto& b = best[root];
  34. for(int to : adj[root]){
  35. if(to==parent) continue;
  36. dfs(to,root);
  37. if(s[to].size()>s[root].size()) swap(s[root],s[to]); // small to large
  38. for(auto it : s[to]){
  39. int w = it.first;
  40. int id = it.second;
  41. b=min(b,w); // this is done to ensure the LCA itself also
  42. if(s[root].count({w,id})) {
  43. s[root].erase({w,id}); // found the LCA of a path query, so delete this from the set.
  44. }
  45. else s[root].insert({w,id});
  46. }
  47. s[to].clear();
  48. }
  49. if(!s[root].empty()) b=min(b,s[root].begin()->first);
  50. };
  51. dfs(0,0);
  52. for(auto i : best) cout << i << '\n';
  53. }
Advertisement
Add Comment
Please, Sign In to add comment