fork download
copy 
  1. //--------my brain isn't at home right now------------------
  2. #include<bits/stdc++.h>  
  3.  
  4. using namespace std; 
  5.  
  6. #define pb push_back
  7. #define fi first
  8. #define se second
  9. #define nl '\n'
  10. typedef long long ll;
  11.  
  12. const int N = 2e5 + 1;
  13. vector<int> g[N];
  14. vector<pair<int, int>> v(N);
  15. ll dp[N];
  16. vector<int> parent(N);
  17.  
  18. void dfs1(int u, int t = -1){
  19.     for(auto x: g[u]){
  20.         if(x == t) continue;
  21.         parent[x] = u;
  22.         dfs1(x, u);
  23.     }
  24. }
  25. void dfs(int u, int k = -1){
  26.     for(auto x: g[u]){
  27.         if(x == k) continue;
  28.         dp[x] += dp[u];
  29.         dfs(x, u);
  30.     }
  31. } 
  32. void Solve(){
  33.     int n;
  34.     cin>>n;
  35.     for(int i = 1; i < n; i++){
  36.         int a, b;
  37.         cin>>a>>b;
  38.         v[i] = {a, b};
  39.         g[a].pb(b); 
  40.         g[b].pb(a);
  41.     }
  42.     for(int i = 0; i < N; i++){
  43.         dp[i] = 0;
  44.         parent[i] = 0;
  45.     }
  46.     dfs1(1);
  47.     int q;
  48.     cin>>q;
  49.     while(q--){
  50.         int t, e, x;
  51.         cin>>t>>e>>x;
  52.         int a = v[e].fi;
  53.         int b = v[e].se;
  54.         if(t == 1){
  55.             if(parent[b] == a){
  56.                 dp[1] += x;
  57.                 dp[b] -= x;
  58.             }
  59.             else{
  60.                 dp[a] += x;
  61.             }
  62.         }
  63.         else{
  64.             if(parent[a] == b){
  65.                 dp[1] += x;
  66.                 dp[a] -= x;
  67.             }
  68.             else{
  69.                 dp[b] += x;
  70.             }
  71.         }
  72.     }
  73.     dfs(1);
  74.     for(int i = 1; i <= n; i++){
  75.         cout<<dp[i]<<nl;
  76.     }
  77.  
  78. }
  79. int main(){  
  80.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  81.     Solve();
  82. }
Time limit exceeded #stdin #stdout 5s 12236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PAEUDp
language:
C++14 (gcc 8.3)
created:
3 years 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!