fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5.  
  6. long long n, q;
  7. long long visited[MaxN], par[MaxN], num[MaxN], dis[MaxN];
  8. vector<long long> a[MaxN];
  9.  
  10. void bfs(long long s)
  11. {
  12.     queue<long long> qu;
  13.     qu.push(s);
  14.     visited[s] = true;
  15.     par[s] = s;
  16.  
  17.     while(!qu.empty())
  18.     {
  19.         long long u = qu.front();
  20.         qu.pop();
  21.  
  22.         for(long long v : a[u])
  23.         {
  24.             if(!visited[v])
  25.             {
  26.                 visited[v] = true;
  27.                 dis[v] = dis[u] + 1;
  28.                 par[v] = u;
  29.                 qu.push(v);
  30.             }
  31.         }
  32.     }
  33. }
  34.  
  35. struct QUERY
  36. {
  37.     long long x, y, z;
  38. } query[MaxN];
  39.  
  40. void input()
  41. {
  42.     cin >> n >> q;
  43.  
  44.     for(long long i = 1; i < n; i++)
  45.     {
  46.         long long u, v;
  47.         cin >> u >> v;
  48.         a[u].push_back(v);
  49.         a[v].push_back(u);
  50.     }
  51.  
  52.     for(long long i = 1; i <= q; i++)
  53.     {
  54.         cin >> query[i].x >> query[i].y >> query[i].z;
  55.     }
  56. }
  57.  
  58. void solve()
  59. {
  60.     bfs(1);
  61.  
  62.     for(long long i = 1; i <= q; i++)
  63.     {
  64.         long long x = query[i].x;
  65.         long long y = query[i].y;
  66.         long long z = query[i].z;
  67.  
  68.         vector<long long> vt;
  69.  
  70.         while(dis[y] > dis[x])
  71.         {
  72.             if(num[y] == 0)
  73.                 num[y] = z;
  74.  
  75.             vt.push_back(y);
  76.             y = par[y];
  77.         }
  78.  
  79.         if(num[x] == 0)
  80.             num[x] = z;
  81.  
  82.         for(long long u : vt)
  83.             par[u] = par[x];
  84.     }
  85.  
  86.     for(long long i = 1; i <= n; i++)
  87.         cout << num[i] << " ";
  88. }
  89.  
  90. int main()
  91. {
  92.     ios_base::sync_with_stdio(0);
  93.     cin.tie(0);
  94.  
  95.     input();
  96.     solve();
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0.01s 9696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9nSh2K
language:
C++14 (gcc 8.3)
created:
2 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!