fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 1000001
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<30)
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q ;
  21. ll a[MAXN] ;
  22. vector<ll> adj[MAXN ] ;
  23.  
  24. pair<ll,ll> dfs(ll u, ll p, bool & check  ) {
  25.     if(a[u]) {
  26.         return {a[u], a[u] } ;
  27.     }
  28.     if(!check ) {
  29.         return {-1, - 1 } ;
  30.     }
  31.     vector<pair<ll,ll>> seg ;
  32.     for(ll v : adj[u]) if(v != p ) {
  33.             seg.push_back(dfs(v, u, check ) ) ;
  34.         }
  35.     vector<pair<ll,ll> > sort_seg = seg ;
  36.     sort(sort_seg.begin(), sort_seg.end() ) ;
  37.     ll pp = -1 ;
  38.     REP(i, sort_seg.size() ) if(sort_seg[0] == seg[i]) pp = i ;
  39.     if(pp == -1 ) {
  40.         check = false ;
  41.         return {- 1, - 1 } ;
  42.     }
  43.  
  44.     REP(i, sort_seg.size() - 1 ) if(sort_seg[i].se + 1 != sort_seg[i + 1].fi ) {
  45.         check = false ;
  46.         return {- 1, - 1 } ;
  47.     }
  48.  
  49.     REP(i,  seg.size() ) if(sort_seg[i] != seg[ (i + pp ) % seg.size() ] ) {
  50.         check = false ;
  51.         return {-1, - 1 } ;
  52.     }
  53.     return {sort_seg.front().fi, sort_seg.back().se } ;
  54. }
  55.  
  56. void init() {
  57.     cin >> n ;
  58.     FOR(i, 2, n ) {
  59.         ll p ;
  60.         cin >> p ;
  61.         adj[i].push_back(p) ;
  62.         adj[p].push_back(i) ;
  63.     }
  64.     FOR(i, 1, n ) cin >> a[i] ;
  65. }
  66.  
  67. void solve() {
  68.     bool check = true ;
  69.  
  70.     pair<ll,ll> res = dfs(1, 1, check ) ;
  71.     ll k = 0;
  72.     FOR(i, 1, n ) k = max(k, a[i]) ;
  73. //    debug(check ) ;
  74. //    debug(res.fi ) ;
  75. //    debug(res.se ) ;
  76.     if(check && res.fi == 1 && res.se == k ) cout << "yes" << el ;
  77.     else cout << "no" << el ;
  78.  
  79.     FOR(i, 1, n ) adj[i].clear() ;
  80. }
  81.  
  82.  
  83. _ROOT_ {
  84. //    freopen(NAME".inp", "r", stdin);
  85. //    freopen(NAME".out", "w", stdout) ;
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(0);
  88.     cout.tie(0);
  89.     int t = 1;
  90.     cin >> t ;
  91.     while(t--) {
  92.         init();
  93.         solve();
  94.     }
  95.     return (0&0);
  96. }
Success #stdin #stdout 0.01s 27332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
no
https://ideone.com/uCVTo3
language:
C++14 (gcc 8.3)
created:
1 day 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!