QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689489#530. ExperienceMher777100 ✓35ms19548kbC++204.6kb2024-10-30 17:20:562024-10-30 17:20:56

Judging History

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

  • [2024-10-30 17:20:56]
  • 评测
  • 测评结果:100
  • 用时:35ms
  • 内存:19548kb
  • [2024-10-30 17:20:56]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(time(nullptr));

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

/* -------------------- Functions -------------------- */

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void precision(int x) {
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}

ll gcd(ll a, ll b) {
    if (a == 0 || b == 0) return(max(a, b));
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll range_sum(ll a, ll b) {
    if (a > b) return 0ll;
    ll dif = a - 1, cnt = b - a + 1;
    ll ans = ((b - a + 1) * (b - a + 2)) / 2;
    ans += ((b - a + 1) * dif);
    return ans;
}

string dec_to_bin(ll a) {
    string s = "";
    for (ll i = a; i > 0; ) {
        ll k = i % 2;
        i /= 2;
        char c = k + 48;
        s += c;
    }
    if (a == 0) {
        s = "0";
    }
    reverse(all(s));
    return s;
}

ll bin_to_dec(string s) {
    ll num = 0;
    for (int i = 0; i < s.size(); i++) {
        num *= 2ll;
        num += (s[i] - '0');
    }
    return num;
}

ll factorial_by_mod(ll n, ll mod) {
    ll ans = 1;
    ll num;
    for (ll i = 1; i <= n; ++i) {
        num = i % mod;
        ans *= num;
        ans %= mod;
    }
    return ans;
}

bool isPrime(ll a) {
    if (a == 1) return false;
    for (ll i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}

ll binpow(ll a, ll b) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

/* -------------------- Solution -------------------- */

const int N = 100005;
ll w[N], dp[N][2];
vi g[N];
int n;

void dfs(int u = 1, int par = 1) {
    ll sum = 0;
    for (auto to : g[u]) {
        if (to == par) continue;
        dfs(to, u);
        sum += max(dp[to][0], dp[to][1]);
    }
    dp[u][0] = dp[u][1] = sum;
    for (auto to : g[u]) {
        if (to == par) continue;
        if (w[u] < w[to]) {
            dp[u][0] = max(dp[u][0], sum - max(dp[to][0], dp[to][1]) + dp[to][0] + w[to] - w[u]);
        }
        if (w[u] > w[to]) {
            dp[u][1] = max(dp[u][1], sum - max(dp[to][0], dp[to][1]) + dp[to][1] + w[u] - w[to]);
        }
    }
}

void slv() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].pub(y);
        g[y].pub(x);
    }
    dfs();
    cout << max(dp[1][0], dp[1][1]);
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    //precision(0);
    cs();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 5808kb

input:

20
988 221 200 538 673 492 988 508 317 764 862 122 174 788 14 11 836 384 832 697
1 18
18 4
4 15
15 2
2 12
12 11
11 3
15 20
20 16
16 5
20 8
18 10
10 7
7 19
19 17
10 9
9 13
9 14
14 6

output:

3782

result:

ok single line: '3782'

Test #2:

score: 10
Accepted
time: 1ms
memory: 5732kb

input:

20
469 574 240 50 824 619 227 657 867 594 369 295 773 681 299 134 559 835 919 709
1 3
3 9
9 15
15 7
7 14
7 4
15 20
20 17
20 6
1 12
12 8
8 11
11 18
18 2
2 19
19 5
5 13
13 10
10 16

output:

3354

result:

ok single line: '3354'

Test #3:

score: 5
Accepted
time: 2ms
memory: 5996kb

input:

5000
446383112 370347851 840127178 90228291 57677664 583710383 412519061 641720279 464924949 486422373 480029067 121149423 912387788 277217055 128527359 116549961 207248103 59876230 741885543 568941804 673081907 332307190 958281929 815704479 578383090 199490588 209097218 742508013 566572131 29772375...

output:

928986137667

result:

ok single line: '928986137667'

Test #4:

score: 5
Accepted
time: 2ms
memory: 8076kb

input:

5000
826441146 196713422 823938896 41688167 174573141 104692893 560459516 882489892 913431807 889932550 143196876 690010325 225423015 580019213 507498831 600424594 551356752 976354201 202289355 627027981 693188010 321855213 677908921 238589823 412111101 811345934 521191506 87443000 357818080 1705613...

output:

962477664815

result:

ok single line: '962477664815'

Test #5:

score: 5
Accepted
time: 2ms
memory: 6052kb

input:

5000
817774958 308298842 638680206 156667574 361414089 873932811 385230258 150178195 681099328 749938926 751190531 61473964 960831054 211897375 474000580 495778670 198397167 544445856 216455701 70016024 175476091 142109303 562843109 992276377 709204676 498007 951030959 250969795 765227850 57341988 5...

output:

940579013096

result:

ok single line: '940579013096'

Test #6:

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

input:

5000
50674193 49527746 713259844 816702729 63543186 93839339 900816058 706830028 244357746 175975802 976476790 86874939 207376701 547442061 754527681 216259012 68755449 635851936 783117650 587038131 71863537 270447099 248412658 114050960 837935934 28789450 588372571 739120873 199606001 500653017 261...

output:

1074869322240

result:

ok single line: '1074869322240'

Test #7:

score: 5
Accepted
time: 2ms
memory: 6340kb

input:

5000
759215003 825188943 167696616 242493548 897569668 105526735 868993417 938626426 169100725 60210953 14537088 968003974 857983088 341147177 189438079 150189234 336025934 70345277 240999363 25005579 525915042 500817394 823213729 907145562 353640734 860138805 31081536 586798400 837847771 189053786 ...

output:

1051826250008

result:

ok single line: '1051826250008'

Test #8:

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

input:

5000
745916812 426411347 698388863 920923680 257440565 228679283 245468551 953557488 720292075 129000228 246617856 813789211 122761867 582878238 116177491 368726673 64541120 978482509 234846591 878086290 169534515 947285297 606315424 513568068 772468224 784176428 659924681 732724267 340784975 529988...

output:

745570211

result:

ok single line: '745570211'

Test #9:

score: 5
Accepted
time: 29ms
memory: 11568kb

input:

100000
867693810 648844535 570453674 958757431 896382549 349851987 18358576 656234598 717540110 392935468 39223789 535516231 737602825 85771402 284422782 574115093 6690453 261108558 841939198 280924679 225902203 740262818 324868518 706169430 845385554 376754115 299974748 219759820 420969519 13457897...

output:

18822805414040

result:

ok single line: '18822805414040'

Test #10:

score: 5
Accepted
time: 23ms
memory: 19548kb

input:

100000
18247397 915000979 371447041 661741351 390512714 676452729 605878501 612650010 194438607 597846232 777940478 645318441 757251279 757451923 260520712 574113469 192251135 29651707 282748315 777644136 392286347 239996732 284021650 583525770 162060828 372095078 109967733 430529096 973891814 75933...

output:

21254579276102

result:

ok single line: '21254579276102'

Test #11:

score: 5
Accepted
time: 35ms
memory: 18288kb

input:

100000
161389642 663588506 103366390 793143682 937306080 827648600 962306414 597600916 619115926 882057937 974721632 816047975 670468173 490821705 783905862 94236821 531366253 144797408 840302361 213781924 782766734 781193401 401220386 586657281 500431227 316253481 387350561 278072251 610808084 9265...

output:

21382476831350

result:

ok single line: '21382476831350'

Test #12:

score: 5
Accepted
time: 18ms
memory: 11440kb

input:

100000
702045748 821173140 738550078 708352869 312332723 339646992 860390809 11035704 801619145 312205745 498300548 662094625 743979516 54071137 672548416 932184948 538483999 458415303 808391409 88513644 799901682 330852653 553882130 448676564 76478273 567922695 423539615 117561654 213494282 7020340...

output:

17635485167868

result:

ok single line: '17635485167868'

Test #13:

score: 5
Accepted
time: 30ms
memory: 11496kb

input:

100000
158602740 857492740 69693659 815945520 901746976 727162271 608595473 634946082 581796946 626782946 209394949 298987934 319658913 397290407 763151192 230102742 873211706 386543670 382020689 744109897 97497456 642764343 145049218 793851217 458842276 821750374 985967314 132708317 365020197 94229...

output:

17677654999138

result:

ok single line: '17677654999138'

Test #14:

score: 5
Accepted
time: 23ms
memory: 15392kb

input:

100000
224779981 177653894 759300343 782328914 197399510 938782497 371062739 119646773 723711481 189099811 370486953 469621819 558878604 770599319 34982989 39714263 775273448 809742406 894201544 135244222 346553754 484154466 654043919 271687006 159999821 148462484 207278818 689359720 244669448 33779...

output:

16985717452674

result:

ok single line: '16985717452674'

Test #15:

score: 5
Accepted
time: 28ms
memory: 13688kb

input:

100000
487205713 31303760 707256248 600328138 11454663 648113519 394087502 117812324 48563676 85033562 847604081 677579139 342407820 31355044 570862159 560833284 157044882 864981683 958621189 462815787 879228984 844281632 455261324 743493965 326179024 24247790 876354510 284824904 237934725 994284272...

output:

12527591432483

result:

ok single line: '12527591432483'

Test #16:

score: 5
Accepted
time: 32ms
memory: 15192kb

input:

100000
144635821 943846990 856239191 209289320 190355387 735502264 282249786 543844314 525744227 263329799 958155782 24697652 290504243 532791573 763738122 350138789 296445175 200937795 582771782 826093082 599265720 259310529 805314200 436816094 493876613 933558154 245482767 411697576 957174428 7300...

output:

17043299358676

result:

ok single line: '17043299358676'

Test #17:

score: 5
Accepted
time: 31ms
memory: 15124kb

input:

100000
737262622 841182884 731123736 84594241 573654482 328873392 895288247 584517841 734755046 164889359 218277214 119840851 759118914 324259288 882572712 937264565 582029647 944043900 719654439 654113244 296943259 796387612 625330766 596668704 479400298 879962861 285666384 725337635 502533732 1556...

output:

16946638251843

result:

ok single line: '16946638251843'

Test #18:

score: 5
Accepted
time: 24ms
memory: 15452kb

input:

100000
153281416 140404555 175376194 638222395 890134696 579022973 67799271 328406846 699934193 440207530 467688185 299324216 61806368 901762441 245249553 400950394 319327705 872948859 513485015 543014816 326527108 237177028 273445032 962687 159341454 789615152 930698528 237241794 975501667 87800901...

output:

16971008806964

result:

ok single line: '16971008806964'