Submission #75090724

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "../../Templates/C++/debug.h"
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define lso(s) ((s) & -(s))
int lg(ll s) { return s ? __builtin_clzll(1) - __builtin_clzll(s) : -1; }//lg(1)=0, lg(2)=1, lg(3)=1, lg(4)=2, ...
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MOD = 998244353;
const double EPS = 1e-9;
const char nl = '\n';
const int INF = 1e9;
const ll INFL = 4e18;
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll floor(ll a, ll b) { return a / b - (a % b < 0); }
ll ceil(ll a, ll b) { return a / b + (a % b > 0); }

template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

mt19937_64 rng(10);//rng(chrono::steady_clock::now().time_since_epoch().count());
ll gen() {
	ll x = 0;
	while(x == 0)
		x = rng() % MOD;
	return x;
}

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}
  mint& operator-=(const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD;return *this;}
  mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}
  mint operator+(const mint a) const {mint res(*this);return res+=a;}
  mint operator-(const mint a) const {mint res(*this);return res-=a;}
  mint operator*(const mint a) const {mint res(*this);return res*=a;}
  mint pow(ll b) const {
    mint res(1), a(*this);
    while (b) {
      if (b & 1) res *= a;
      a *= a;
      b >>= 1;
    }
    return res;
  }
  // for prime MOD
  mint inv() const {return pow(MOD-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint operator/(const mint a) const {mint res(*this);return res/=a;}
};
ostream& operator<<(ostream& os, const mint& a) {os << a.x; return os;}

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct LCA {
	int T = 0;
	vi time, path, ret;
	RMQ<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	//dist(a,b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};

void solve() {
    int N, seed, M, F; cin >> N >> seed >> M >> F;
    vi q(M), d(M); for(int i = 1; i < M; i++) cin >> q[i];
    cin >> d;
    
    vi p(N), c(N);
    ll state = seed;
    for(int i = 1; i < N; i++) {
        if(i < M) p[i] = q[i];
        else {
            p[i] = state % i + 1;
            state = (state * 1103515245 + 12345) % (1LL << 31);
        }
    }
    for(int i = 0; i < N; i++) {
        if(i < M) {
            c[i] = d[i];
        } else {
            c[i] = state % F + 1;
            state = (state * 1103515245 + 12345) % (1LL << 31);
        }
    }

    for(auto& x : c) x--;
    vector<vector<int>> al(N);
    for(int i = 1; i < N; i++) {
        al[p[i] - 1].pb(i);
    }

    LCA lca(al);
    vector<basic_string<int>> vec(N);
    vi t(N);
    int tt = 0;
    auto dfs = [&](auto&& dfs, int u)->void {
        t[u] = tt++;
        vec[c[u]].pb(u);
        for(int v : al[u]) {
            dfs(dfs, v);
        }
    };
    dfs(dfs, 0);

    vi ma(N), ct(N);
    vector<basic_string<int>> al2(N);
    for(int i = 0; i < N; i++) {
        if(sz(vec[i]) == 0) continue;
        stack<int> s;
        basic_string<int> hmm;
        auto add = [&](int x) {
            while(sz(s) > 0 && lca.lca(s.top(), x) != s.top()) {
                s.pop();
            }
            if(sz(s) && s.top() != x) {
                al2[s.top()].pb(x);
                hmm.pb(s.top());
            }
            if(!sz(s) || s.top() != x) s.push(x);
        };
        basic_string<int> vv;
        for(int j = 0; j < sz(vec[i]); j++) {
            vv.pb(vec[i][j]);
            if(j < sz(vec[i]) - 1) {
                vv.pb(lca.lca(vec[i][j], vec[i][j + 1]));
            }
        }
        sort(all(vv), [&](int x, int y) {
            return t[x] < t[y];
        });
        for(auto x : vv) add(x);
        while(sz(s) > 1) s.pop();
        int r = s.top();
        auto dfs = [&](auto&& dfs, int u)->int {
            int cnt = c[u] == i;
            int cc = 0;
            for(int v : al2[u]) {
                int res = dfs(dfs, v);
                cnt += res;
                cc += res > 0;
            }
            if(c[u] != i && cc <= 1) {
                return cnt;
            }
            if(ma[u] == cnt) ct[u]++;
            else if(ma[u] < cnt) {
                ma[u] = cnt;
                ct[u] = 1;
            }
            return cnt;
        };
        dfs(dfs, r);
        for(auto x : hmm) al2[x].clear();
    }

    auto rec = [&](auto&& rec, int u)->void {
        for(int v : al[u]) {
            rec(rec, v);
            if(ma[v] == ma[u]) ct[u] += ct[v];
            else if(ma[v] > ma[u]) {
                ma[u] = ma[v];
                ct[u] = ct[v];
            }
        }
    };
    rec(rec, 0);

    mint x = 0;
    for(int i = 0; i < N; i++) {
        x += 1LL * (ma[i] ^ (i + 1)) * (ct[i] ^ (i + 1));
    }
    cout << x << nl;
}
/*

[c = {5,3,1,3,4,2,2,2,4,2,2,5,3,5,3}]
0 {1,5,11}
1 {2,4,13}
2 {3}
3 {6}
4 {9}
5 {8}
6 {7}
7 {14}
8 {}
9 {10,12}
10{}
11{}
12{}
13{}
14{}
*/


int main() {
    //魔法はイメージの世界
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
	return 0;
}

Submission Info

Judge Result