QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641928#6160. 树Elegia100 ✓429ms280500kbC++142.5kb2024-10-15 03:21:502024-10-15 03:21:51

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 03:21:51]
  • 评测
  • 测评结果:100
  • 用时:429ms
  • 内存:280500kb
  • [2024-10-15 03:21:50]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &x : v) is >> x;
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    if (!v.empty()) {
        os << v.front();
        for (int i = 1; i < v.size(); ++i) os << ' ' << v[i];
    }
    return os;
}

const int N = 525105, L = 21;

namespace Trie {

struct Node {
    int par, xsum;
    int ch[2];
} P[N * (L + 1)];

int top;

void update(int o, int l) {
    P[o].xsum = P[P[o].ch[0]].xsum ^ P[P[o].ch[1]].xsum ^ (P[P[o].ch[1]].par << l);
    P[o].par = P[P[o].ch[0]].par ^ P[P[o].ch[1]].par;
}

void carry(int o, int l) {
    if (!o || l == L)
        return;
    swap(P[o].ch[0], P[o].ch[1]);
    carry(P[o].ch[0], l + 1);
    update(o, l);
}

int merge(int x, int y) {
    if (!x || !y)
        return x ^ y;
    P[x].par ^= P[y].par;
    P[x].xsum ^= P[y].xsum;
    for (int i = 0; i < 2; ++i) P[x].ch[i] = merge(P[x].ch[i], P[y].ch[i]);
    return x;
}

int single(int x, int l) {
    int o = ++top;
    P[o].par = 1;
    if (l == L)
        return o;
    P[o].ch[(x >> l) & 1] = single(x, l + 1);
    update(o, l);
    return o;
}

}  // namespace Trie

int n;
int v[N];
vector<int> g[N];

ll ans;

int dfs(int u) {
    int ret = 0;
    for (int gv : g[u]) ret = Trie::merge(ret, dfs(gv));
    Trie::carry(ret, 0);
    ret = Trie::merge(ret, Trie::single(v[u], 0));
    ans += Trie::P[ret].xsum;
    return ret;
}

int main() {
#ifdef ELEGIA
    freopen("test.in", "r", stdin);
    int nol_cl = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    dfs(1);
    cout << ans << '\n';

#ifdef ELEGIA
    LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 20428kb

input:

1501
524935 524911 524956 524964 525002 524945 524944 524954 524980 525009 524971 524989 524955 524962 524933 524935 524938 524973 524931 524933 524939 524994 524948 524912 27768 524937 482489 525001 524961 524964 524988 524959 524984 43791 525005 524911 524929 524952 524944 524918 524924 524961 524...

output:

701627312

result:

ok 1 number(s): "701627312"

Test #2:

score: 5
Accepted
time: 4ms
memory: 20252kb

input:

2501
524935 524987 524985 15371 521077 524914 358211 524917 524933 524940 524997 524965 525010 508291 509667 525010 34977 524932 525001 524931 524927 524931 524942 524978 524940 524999 48818 524991 524942 524983 524953 524952 524932 524911 524996 524980 524926 524978 524988 524930 524951 524933 5249...

output:

1248760886

result:

ok 1 number(s): "1248760886"

Test #3:

score: 5
Accepted
time: 55ms
memory: 62148kb

input:

100000
524940 524940 524924 524939 524984 524915 524961 524980 525007 524983 525000 524949 525003 183887 203283 524986 524948 524943 524962 524962 524951 524938 524971 524944 524978 353146 524954 288731 524914 524927 524930 524964 524939 524977 524968 524937 524930 524931 525005 524917 524935 524953...

output:

48847009165

result:

ok 1 number(s): "48847009165"

Test #4:

score: 5
Accepted
time: 51ms
memory: 62420kb

input:

100000
525001 524945 300466 524918 524993 524942 524980 524940 524958 524982 524985 524930 525000 524914 524979 524916 524986 524952 524991 525010 524943 525003 404403 363004 524963 524999 524937 524940 307161 524926 524982 524988 524916 524987 524960 524993 524969 524946 524933 524951 524941 524920...

output:

48821541653

result:

ok 1 number(s): "48821541653"

Test #5:

score: 5
Accepted
time: 56ms
memory: 61360kb

input:

100000
524983 525002 524939 524914 524941 29526 73021 524953 524927 525007 524993 524982 524976 524975 524981 524950 524970 524937 524980 524916 524979 524983 55981 524985 524975 524969 524982 524921 524985 459301 525008 524911 524932 524954 524952 524952 524959 306535 524989 524989 524987 524951 52...

output:

48815029002

result:

ok 1 number(s): "48815029002"

Test #6:

score: 5
Accepted
time: 82ms
memory: 83644kb

input:

152501
524982 524933 525002 524967 82725 253741 524911 524981 524972 524935 244289 524931 524957 524927 524940 524960 524932 150931 524974 524920 524975 524940 525008 524963 71995 525001 524997 524974 69275 146625 459556 524968 524919 447791 524928 524983 524953 524963 524959 524985 524999 249653 52...

output:

74328889396

result:

ok 1 number(s): "74328889396"

Test #7:

score: 5
Accepted
time: 77ms
memory: 83672kb

input:

152501
524970 524966 524938 524994 525004 524921 188941 525008 524943 524917 524999 524997 284880 524976 524946 524994 524976 524923 524960 524990 524917 525005 524987 524961 525009 254221 524982 108142 524971 524988 524927 524915 524983 524961 524951 524988 524985 525001 524936 524921 524973 524949...

output:

74602741206

result:

ok 1 number(s): "74602741206"

Test #8:

score: 5
Accepted
time: 79ms
memory: 83572kb

input:

152501
524980 524993 525005 524943 524950 524998 524990 524952 261512 524968 524918 524973 524976 524920 524951 524952 524965 524966 524914 524976 524937 524917 524914 524911 524991 524997 524974 524964 524945 524941 524920 524916 524971 192185 524971 524926 524959 524971 524973 524911 524921 524997...

output:

74603663049

result:

ok 1 number(s): "74603663049"

Test #9:

score: 5
Accepted
time: 396ms
memory: 280412kb

input:

525010
524955 524979 495345 524927 524966 524997 524942 138576 524956 524989 524940 524969 360541 524997 524952 524997 524933 524931 524958 524987 524933 524941 407091 524952 524951 524972 524998 524913 524955 524948 524988 524920 524981 524999 524985 525002 524940 524976 524956 524920 524921 524978...

output:

275846381079

result:

ok 1 number(s): "275846381079"

Test #10:

score: 5
Accepted
time: 429ms
memory: 280480kb

input:

525010
410691 524927 524994 524983 524994 524996 524933 524973 525009 331627 524951 524998 171113 524978 524960 525000 69833 524948 525002 524919 525001 294363 524925 263273 116049 524946 524993 524976 524961 524936 524968 7337 524987 524981 524925 260013 524931 427126 524993 524962 524950 524956 52...

output:

275754326799

result:

ok 1 number(s): "275754326799"

Test #11:

score: 5
Accepted
time: 380ms
memory: 280464kb

input:

525010
524949 524945 524932 524948 524918 524939 524958 524963 524923 524995 524981 524950 524927 524929 524945 524972 524911 524961 524913 524949 524986 524934 524971 524925 524950 524957 524919 524945 524982 524929 524982 524926 524938 331619 524965 524934 524929 524949 524917 524978 337295 524919...

output:

275940487293

result:

ok 1 number(s): "275940487293"

Test #12:

score: 5
Accepted
time: 367ms
memory: 280500kb

input:

525010
524926 524992 524936 524979 524925 524994 525001 524946 524981 524922 524993 436287 525002 524939 525007 524926 524986 524975 524986 524961 524932 525007 524935 524948 524988 524972 524963 524956 524960 38337 524932 524924 524996 524955 524986 524976 524966 524973 524983 524991 524965 524978 ...

output:

275983685105

result:

ok 1 number(s): "275983685105"

Test #13:

score: 5
Accepted
time: 257ms
memory: 242840kb

input:

525010
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

23032985474

result:

ok 1 number(s): "23032985474"

Test #14:

score: 5
Accepted
time: 266ms
memory: 242896kb

input:

525010
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

22985217528

result:

ok 1 number(s): "22985217528"

Test #15:

score: 5
Accepted
time: 252ms
memory: 242700kb

input:

525010
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

23007875223

result:

ok 1 number(s): "23007875223"

Test #16:

score: 5
Accepted
time: 269ms
memory: 242744kb

input:

525010
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

23045778723

result:

ok 1 number(s): "23045778723"

Test #17:

score: 5
Accepted
time: 317ms
memory: 242900kb

input:

525010
524997 524962 524959 525010 524997 524946 524992 524974 524978 524988 524983 524960 524949 524922 524948 524925 179739 374866 524976 113487 524978 524936 524931 524912 524993 524933 524947 524940 524947 524949 525008 525006 524928 524979 524966 524925 524993 524917 524915 524969 524997 524936...

output:

256639673082

result:

ok 1 number(s): "256639673082"

Test #18:

score: 5
Accepted
time: 323ms
memory: 242840kb

input:

525010
524939 524971 524960 524991 524958 524977 525000 524920 524937 524925 524933 524944 524977 524921 524975 524942 524933 524998 524913 524938 524937 524980 525004 524986 15097 20701 524986 525008 524943 258327 525008 524982 524925 524956 439611 524955 42646 46145 525009 524957 524961 524946 524...

output:

256545959720

result:

ok 1 number(s): "256545959720"

Test #19:

score: 5
Accepted
time: 343ms
memory: 242840kb

input:

525010
524913 524930 525002 524948 524945 524933 524990 524998 525001 524995 524974 524912 524950 524951 524951 524960 524928 524927 524911 350625 524991 178441 300871 524988 524982 524949 325161 524957 524999 332281 525005 524913 524960 524998 525006 199811 525008 524960 338801 524944 524953 524935...

output:

256775767753

result:

ok 1 number(s): "256775767753"

Test #20:

score: 5
Accepted
time: 319ms
memory: 242756kb

input:

525010
524951 524981 524977 524964 524942 524945 524936 524994 524959 524920 524971 524979 524945 365305 524992 524945 525001 524979 524951 524951 524994 524955 524975 524937 524939 524913 524963 524960 524977 524949 524970 524995 524978 524989 524912 524933 524998 524999 524992 524983 524956 156707...

output:

256735623773

result:

ok 1 number(s): "256735623773"

Extra Test:

score: 0
Extra Test Passed