Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define all(x) begin(x),end(x)
- template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
- 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; }
- #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
- typedef long long ll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int,int> pi;
- const int mxN = 1e5+1, oo = 1e9;
- /*
- 4
- 1 2
- 2 3
- 2 4
- 4
- 1 4 5
- 1 2 3
- 2 3 2
- 3 4 1
- */
- int main() {
- int n; cin >> n;
- vvi adj(n);
- for(int i=0;i<n-1;++i) {
- int u,v; cin >> u >> v;
- --u,--v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- int q; cin >> q;
- vector<set<pi>> s(n);
- while(q--) {
- int u,v,w; cin >> u >> v >> w;
- --u,--v;
- s[u].insert({w,q});
- s[v].insert({w,q});
- }
- vi best(n,oo);
- auto dfs = [&](auto&& self, int at, int from) -> void {
- auto& b = best[at];
- for(int to : adj[at]) if(to!=from) {
- self(self,to,at);
- if(s[to].size()>s[at].size()) swap(s[at],s[to]); // small to large
- for(auto [w,id] : s[to]) {
- b=min(b,w); // this is done to ensure the LCA itself also
- if(s[at].count({w,id})) {
- s[at].erase({w,id}); // found the LCA of a path query, so delete this from the set.
- } else s[at].insert({w,id});
- }
- s[to].clear();
- }
- if(!s[at].empty()) b=min(b,s[at].begin()->first);
- };
- dfs(dfs,0,0);
- for(auto i : best) cout << i << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment