fork download
copy 
  1. /*
  2. ye mera template hai
  3. apna khud likho bc :P
  4. */
  5.  
  6. /*
  7. Author : Sarvagya Agarwal
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12.  
  13. //defines
  14. #define openin freopen("input.txt","r",stdin)
  15. #define openout freopen("output.txt","w",stdout)
  16. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  17. #define ll long long
  18. #define int long long
  19. #define mod 1000000007
  20. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  21. #define all(c) (c).begin(),(c).end()
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. int power(int a , int b)
  28. {
  29.     int res = 1 ;
  30.     while(b)
  31.     {
  32.         if(b%2) {
  33.             res = (res * a)%mod ;
  34.         }
  35.         b/=2 ;
  36.         a = (a*a)%mod ;
  37.     }
  38.     return res ;
  39. }
  40.  
  41. //debug
  42. #define TRACE
  43.  
  44. #ifdef TRACE
  45. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  46. template <typename Arg1>
  47. void __f(const char* name, Arg1&& arg1){
  48. 		cerr << name << " : " << arg1 << std::endl;
  49. }
  50. template <typename Arg1, typename... Args>
  51. void __f(const char* names, Arg1&& arg1, Args&&... args){
  52. 		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  53. }
  54. #else
  55. #define trace(...)
  56. #endif
  57.  
  58. const int MAXN = 1e5+5 ;
  59.  
  60. int sum = 0 , n , sz[MAXN] , weight[MAXN] ,parent[MAXN];
  61. vector<int> graph[MAXN] ;
  62. set<int> tree[MAXN] ;
  63. int st[MAXN] , en[MAXN] ;
  64. int gt = 1 ;
  65. void dfs(int node = 1)
  66. {
  67.     st[node] = gt++ ;
  68.     sz[node] = weight[node] ;
  69.     tree[node].insert(node) ;
  70.     for(auto child : graph[node]) {
  71.         if(child != parent[node]) {
  72.             dfs(child) ;
  73.             sz[node] += sz[child] ;
  74.             tree[node].insert(all(tree[child])) ;
  75.         }
  76.     }
  77.     en[node] = gt++ ;
  78. }
  79. bool is_ancestor(int Y,int X)
  80. {
  81.     return st[Y] < st[X] && en[Y] > st[X] ;
  82. }
  83. int32_t main()
  84. {
  85.     fast;
  86.     cin >> n ;
  87.     for(int i = 1 ; i <= n ; ++i) {
  88.         cin >> weight[i] ;
  89.         sum += weight[i] ;
  90.     }
  91.     parent[1] = 0 ;
  92.     for(int i = 2 ; i <= n ; ++i) {
  93.         cin >> parent[i] ;
  94.         graph[parent[i]].emplace_back(i) ;
  95.         graph[i].emplace_back(parent[i]) ;
  96.     }
  97.     dfs() ;
  98.     int q ;
  99.     cin >> q ;
  100.     int X = 1 ;
  101.     while(q--)
  102.     {
  103.         char c ;
  104.         cin >> c ;
  105.         if(c=='S') {
  106.             int Y ;
  107.             cin >> Y ;
  108.             if(X==Y) {
  109.                 cout << sum << '\n' ;
  110.             }
  111.             else if(is_ancestor(Y,X)) {
  112.                 for(auto &child : graph[Y]) {
  113.                     if(tree[child].find(X) != tree[child].end()) {
  114.                         cout << sum - sz[child] << '\n' ;
  115.                         break ;
  116.                     }
  117.                 }
  118.             }
  119.             else {
  120.                 cout << sz[Y] << '\n' ;
  121.             }
  122.         }
  123.         else {
  124.             int root ;
  125.             cin >> root ;
  126.             X = root ;
  127.         }
  128.     }
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0s 10888KB
comments (?)
stdin
copy 
5
2 1 1 1 2
1 1 2 2
3
S 2
R 2
S 1
stdout
copy 
4
3
https://ideone.com/uHBRj4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!