QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#757404#1221. 情报中心I_be_wanna100 ✓1154ms76092kbC++2010.7kb2024-11-17 06:46:082024-11-17 06:46:09

Judging History

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

  • [2024-11-17 06:46:09]
  • 评测
  • 测评结果:100
  • 用时:1154ms
  • 内存:76092kb
  • [2024-11-17 06:46:08]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define re register
#define cs const

namespace IO {

inline char gc()
{
    static cs int Rlen = 1 << 22 | 1;
    static char buf[Rlen], *p1, *p2;
    return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, Rlen, stdin), p1 == p2) ? EOF : *p1++;
} template<typename T>T get_integer()
{
    char c;
    bool f = false;

    while (!isdigit(c = gc()))
        f = c == '-';

    T x = c ^ 48;

    while (isdigit(c = gc()))
        x = ((x + (x << 2)) << 1) + (c ^ 48);

    return f ? -x : x;
} inline int gi()
{
    return get_integer<int>();
}
inline ll gl()
{
    return get_integer<ll>();
}

} using namespace IO;

using std::cerr;
using std::cout;

template<typename T, typename BT>
void ckmx(T &a, cs BT &b)
{
    a < b ? a = b : a;
}

cs int N = 5e4 + 7, M = 1e5 + 7;

int n, m;
int el[N], nx[N + N], to[N + N], w[N + N], ec;
inline void adde(int u, int v, int vl)
{
    nx[++ec] = el[u], el[u] = ec, to[ec] = v, w[ec] = vl;
    nx[++ec] = el[v], el[v] = ec, to[ec] = u, w[ec] = vl;
}

int d[N], fa[N], top[N];
int son[N], sz[N], dfn[N], dfc;
ll len[N];
void dfs1(int u, int p)
{
    fa[u] = p, d[u] = d[p] + 1, sz[u] = 1, son[u] = 0;

    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != p)
        {
            len[to[e]] = len[u] + w[e];
            dfs1(to[e], u);
            sz[u] += sz[to[e]];

            if (sz[to[e]] > sz[son[u]])
                son[u] = to[e];
        }
}

void dfs2(int u, int tp)
{
    top[u] = tp, dfn[u] = ++dfc;

    if (son[u])
        dfs2(son[u], tp);

    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != fa[u] && to[e] != son[u])
            dfs2(to[e], to[e]);
}

int LCA(int u, int v)
{
    while (top[u] != top[v])
        d[top[u]] > d[top[v]] ? u = fa[top[u]] : v = fa[top[v]];

    return d[u] < d[v] ? u : v;
}

ll dis(int u, int v)
{
    return len[u] + len[v] - len[LCA(u, v)] * 2;
}

cs ll INF = 1e17;

int x[M], y[M], p[M];
ll vl[M], cost[M], ans;
std::vector<int> id[N];

namespace S1 {

int rt[N];

cs int N =::N * 100;

int lc[N], rc[N], tot;
ll v1[N], v2[N], dlt;

int node()
{
    int u = ++tot;
    lc[u] = rc[u] = 0;
    v1[u] = v2[u] = -INF;
    return u;
}

void ins(int &u, int l, int r, int p, ll _v1, ll _v2)
{
    if (!u)
        u = node();

    ckmx(v1[u], _v1);
    ckmx(v2[u], _v2);

    if (l == r)
        return;

    int m = (l + r) >> 1;
    p <= m ? ins(lc[u], l, m, p, _v1, _v2) : ins(rc[u], m + 1, r, p, _v1, _v2);
} void del(int &u, int l, int r, int p)
{
    if (!u)
        return;

    if (l == r)
    {
        u = 0;
        return;
    }

    int m = (l + r) >> 1;
    p <= m ? del(lc[u], l, m, p) : del(rc[u], m + 1, r, p);
    v1[u] = std::max(v1[lc[u]], v1[rc[u]]);
    v2[u] = std::max(v2[lc[u]], v2[rc[u]]);

    if (!lc[u] && !rc[u])
        u = 0;
} void merge(int &u, int v, int l, int r)
{
    if (!u || !v)
    {
        u |= v;
        return;
    }

    ckmx(v1[u], v1[v]);
    ckmx(v2[u], v2[v]);

    if (l == r)
        return;

    int m = (l + r) >> 1;
    ckmx(ans, std::max(v1[lc[u]] + v2[rc[v]], v1[lc[v]] + v2[rc[u]]) - dlt);
    merge(lc[u], lc[v], l, m);
    merge(rc[u], rc[v], m + 1, r);
}

void work(int u)
{
    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != fa[u])
            work(to[e]);

    dlt = len[u];

    for (int re i : id[u])
    {
        int tmp = 0;
        ins(tmp, 1, n, d[p[i]], vl[i], vl[i] + len[p[i]]);
        merge(rt[u], tmp, 1, n);
    }

    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != fa[u])
        {
            int v = to[e];
            del(rt[v], 1, n, d[u]);
            merge(rt[u], rt[v], 1, n);
        }
}

void Main()
{
    for (int re i = 1; i <= n; ++i)
        id[i].clear(), rt[i] = 0;

    for (int i = 1; i <= m; ++i)
    {
        if (x[i] != p[i])
            id[x[i]].push_back(i);

        if (y[i] != p[i])
            id[y[i]].push_back(i);
    }

    tot = 0;
    v1[0] = v2[0] = -INF;
    work(1);
}

}

namespace S2 {

int st[N], tp;
int vt[M + M], ct;
ll ans;

struct atom
{
    int u;
    ll vl;
};
typedef std::pair<atom, atom> Atom;
Atom t[N];
#define fi first
#define se second

ll dis(cs atom &a, cs atom &b)
{
    if (!a.u && !b.u)
        return -INF * 10;

    if (!a.u || !b.u)
        return -INF * 5;

    return ::dis(a.u, b.u) + a.vl + b.vl;
}

Atom merge(cs Atom &a, cs Atom &b, bool upt, ll dlt)
{
    ll d00 = dis(a.fi, b.fi), d01 = dis(a.fi, b.se);
    ll d10 = dis(a.se, b.fi), d11 = dis(a.se, b.se);

    if (upt)
        ckmx(ans, std::max({d00, d01, d10, d11}) + dlt);
    ll da = dis(a.fi, a.se), db = dis(b.fi, b.se);
    ll mx = std::max({d00, d01, d10, d11, da, db});

    if (mx == d00)
        return {a.fi, b.fi};

    if (mx == d01)
        return {a.fi, b.se};

    if (mx == d10)
        return {a.se, b.fi};

    if (mx == d11)
        return {a.se, b.se};

    if (mx == da)
        return a;

    if (mx == db)
        return b;

    assert(0);
    return Atom({0, 0}, {0, 0});
}

void solve(int rt)
{
    ct = 0;

    for (int i : id[rt])
        vt[++ct] = x[i], vt[++ct] = y[i];

    vt[++ct] = rt;
    std::sort(vt + 1, vt + ct + 1,
              [](int u, int v)
    {
        return dfn[u] < dfn[v];
    });
    ct = std::unique(vt + 1, vt + ct + 1) - vt - 1;

    for (int re i = 1; i <= ct; ++i)
        t[vt[i]] = Atom({0, 0}, {0, 0});

    for (int i : id[rt])
    {
        t[x[i]] = merge(t[x[i]], Atom({y[i], vl[i] - cost[i] + len[x[i]]}, {0, 0}), x[i] != rt, -len[x[i]] * 2);
        t[y[i]] = merge(t[y[i]], Atom({x[i], vl[i] - cost[i] + len[y[i]]}, {0, 0}), y[i] != rt, -len[y[i]] * 2);
    }

    tp = 0;

    for (int re i = 1; i <= ct; ++i)
    {
        int u = vt[i];

        if (tp)
        {
            int p = LCA(st[tp], u);

            while (d[st[tp]] > d[p])
            {
                int v = st[tp], w = st[tp - 1];

                if (d[w] >= d[p])
                    t[w] = merge(t[w], t[v], w != rt, -len[w] * 2), --tp;
                else
                    t[p] = t[v], st[tp] = p;
            }
        }

        st[++tp] = u;
    }

    while (tp > 1)
    {
        int u = st[tp], v = st[--tp];
        t[v] = merge(t[v], t[u], v != rt, -len[v] * 2);
    }
}

void Main()
{
    ans = -INF * 2;

    for (int re i = 1; i <= n; ++i)
        id[i].clear();

    for (int i = 1; i <= m; ++i)
        id[p[i]].push_back(i);

    for (int re i = 1; i <= n; ++i)
        solve(i);

    ckmx(::ans, ans / 2);
}

}

void Main()
{
    int T = gi();

    while (T--)
    {
        n = gi();
        memset(el, 0, sizeof(int) * (n + 1));
        ec = 0;

        for (int re i = 1; i < n; ++i)
        {
            int u = gi(), v = gi();
            adde(u, v, gi());
        }

        dfc = 0, dfs1(1, 0), dfs2(1, 1);
        m = gi();

        for (int re i = 1; i <= m; ++i)
        {
            x[i] = gi(), y[i] = gi(), cost[i] = gl();

            if (x[i] == y[i])
            {
                --i, --m;
                continue;
            }

            p[i] = LCA(x[i], y[i]);
            vl[i] = len[x[i]] + len[y[i]] - len[p[i]] * 2 - cost[i];
        }

        ans = -INF / 2;
        S1::Main();
        S2::Main();

        if (ans == -INF / 2)
            cout << "F\n";
        else
            cout << ans << "\n";
    }
}
signed main()
{
    Main();
    return 0;
}
/*#include <bits/stdc++.h>
#define ll long long
#define re register
#define cs const

namespace IO {

inline char gc()
{
    static cs int Rlen = 1 << 22 | 1;
    static char buf[Rlen], *p1, *p2;
    return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, Rlen, stdin), p1 == p2) ? EOF : *p1++;
} template<typename T>T get_integer()
{
    char c;
    bool f = false;

    while (!isdigit(c = gc()))
        f = c == '-';

    T x = c ^ 48;

    while (isdigit(c = gc()))
        x = ((x + (x << 2)) << 1) + (c ^ 48);

    return f ? -x : x;
} inline int gi()
{
    return get_integer<int>();
}
inline ll gl()
{
    return get_integer<ll>();
}

} using namespace IO;

using std::cerr;
using std::cout;

template<typename T, typename BT>
void ckmx(T &a, cs BT &b)
{
    a < b ? a = b : a;
}

cs int N = 5e4 + 7, M = 1e5 + 7;

int n, m;
int el[N], nx[N + N], to[N + N], w[N + N], ec;
inline void adde(int u, int v, int vl)
{
    nx[++ec] = el[u], el[u] = ec, to[ec] = v, w[ec] = vl;
    nx[++ec] = el[v], el[v] = ec, to[ec] = u, w[ec] = vl;
}

int d[N], fa[N], top[N];
int son[N], sz[N], dfn[N], dfc;
ll len[N];
void dfs1(int u, int p)
{
    fa[u] = p, d[u] = d[p] + 1, sz[u] = 1, son[u] = 0;

    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != p)
        {
            len[to[e]] = len[u] + w[e];
            dfs1(to[e], u);
            sz[u] += sz[to[e]];

            if (sz[to[e]] > sz[son[u]])
                son[u] = to[e];
        }
}

void dfs2(int u, int tp)
{
    top[u] = tp, dfn[u] = ++dfc;

    if (son[u])
        dfs2(son[u], tp);

    for (int re e = el[u]; e; e = nx[e])
        if (to[e] != fa[u] && to[e] != son[u])
            dfs2(to[e], to[e]);
}

int LCA(int u, int v)
{
    while (top[u] != top[v])
        d[top[u]] > d[top[v]] ? u = fa[top[u]] : v = fa[top[v]];

    return d[u] < d[v] ? u : v;
}

ll dis(int u, int v)
{
    return len[u] + len[v] - len[LCA(u, v)] * 2;
}

cs ll INF = 1e17;

int x[M], y[M], p[M];
ll vl[M], cost[M], ans;
std::vector<int> id[N];

namespace S1 {

int rt[N];

cs int N =::N * 100;

int lc[N], rc[N], tot;
ll v1[N], v2[N], dlt;

int node()
{
    int u = ++tot;
    lc[u] = rc[u] = 0;
    v1[u] = v2[u] = -INF;
    return u;
}

void ins(int &u, int l, int r, int p, ll _v1, ll _v2)
{
    if (!u)
        u = node();

    ckmx(v1[u], _v1);
    ckmx(v2[u], _v2);

    if (l == r)
        return;

    int m = (l + r) >> 1;
    p <= m ? ins(lc[u], l, m, p, _v1, _v2) : ins(rc[u], m + 1, r, p, _v1, _v2);
} void del(int &u, int l, int r, int p)
{
    if (!u)
        return;

    if (l == r)
    {
        u = 0;
        return;
    }

    int m = (l + r) >> 1;
    p <= m ? del(lc[u], l, m, p) : del(rc[u], m + 1, r, p);
    v1[u] = std::max(v1[lc[u]], v1[rc[u]]);
    v2[u] = std::max(v2[lc[u]], v2[rc[u]]);

    if (!lc[u] && !rc[u])
        u = 0;
} void merge(int &u, int v, int l, int r)
{
    if (!u || !v)
    {
        u |= v;
        return;
    }

    ckmx(v1[u], v1[v]);
    ckmx(v2[u], v2[v]);

    if (l == r)
        return;

    int m = (l + r) >> 1;
}*/

詳細信息


Pretests


Final Tests

Test #1:

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

input:

50
2
1 2 746646706
3
2 2 158805763
2 2 0
1 2 2769010819
2
1 2 914572059
3
1 2 213930211
1 2 0
2 2 0
2
1 2 34149275
3
2 2 0
2 2 149024832
1 2 51053526
2
1 2 254241277
3
1 2 1309599026
2 2 595790294
2 2 0
2
1 2 924293412
3
2 2 0
1 2 70948322
1 2 0
2
1 2 120085940
3
2 2 1098008767
1 2 810803844
2 2 0
2...

output:

F
700641848
F
F
853345090
F
F
F
F
-335765973
-110088395
628034705
-739879674
F
-230306371
F
-930847753
F
F
F
-30368435
-968210783
F
-37453013
F
504996844
-691329611
-372260994
F
-368763136
F
F
F
-736440738
-810618582
-962172530
-932830591
F
F
F
F
-550044940
F
F
F
401662489
887352043
F
F
F

result:

ok 50 lines

Test #2:

score: 5
Accepted
time: 3ms
memory: 18028kb

input:

50
10
1 2 831025401
2 3 17043499
1 4 749476846
4 5 605299999
5 6 350873404
6 7 300659907
3 8 406207791
2 9 612660130
7 10 685646376
30
5 6 5064476579
8 8 0
10 10 0
4 5 3660445897
5 10 0
1 9 3660446885
6 7 5064475522
10 10 0
9 9 0
9 5 2865312306
5 7 5064476497
1 2 3660446441
10 10 0
9 9 0
7 10 506447...

output:

-3727295827
94493183
-14678941917
-5574054938
-7077139744
-10056542275
-854708313
-1232365188
-1624606576
-3583909712
-4938133815
-3390253798
-2510752091
-3034158008
-9061709536
-4499610484
-16383580023
-3540735974
-5742888154
-13867296727
-129275888
-11268675743
-3506123988
-13061258642
-1259273401...

result:

ok 50 lines

Test #3:

score: 5
Accepted
time: 3ms
memory: 18340kb

input:

50
200
1 2 132111514
2 3 218131072
3 4 457215808
4 5 210986346
5 6 32656300
6 7 953848206
7 8 154372080
4 9 645141857
9 10 130431237
10 11 415254862
11 12 4997839
8 13 390836759
13 14 640820749
14 15 434042079
15 16 104914370
13 17 363230490
17 18 580147701
17 19 673888862
18 20 464984592
18 21 8971...

output:

-261752610227
-337359051035
-343052587137
-328746209177
-383230409943
-330260132899
-368099811256
-377000149542
-396003263288
-356047137666
-371526095741
-382726097943
-387226690572
-352656304895
-359667344913
-272902489670
-364540214399
-375996045862
-338606666535
-345324110277
-351499738971
-29117...

result:

ok 50 lines

Test #4:

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

input:

50
1000
1 2 439832276
2 3 836243890
3 4 799707681
4 5 879910718
5 6 261426008
6 7 321744006
7 8 644692206
8 9 513339643
9 10 707526649
10 11 390866232
11 12 180191034
12 13 866347596
13 14 702663145
14 15 662968598
15 16 516515411
16 17 905600811
17 18 85093051
18 19 348354946
19 20 542342095
20 21 ...

output:

-387043132469
-340561505600
75567699398
-89729188682
-353407501761
204502503267
-30243132977
-478835907355
-1086596461168
2199418250
-30315033115
-241651591563
-27953672042
-153026465316
-30643558892
-132251459569
260936547737
7935009036
-68295008622
-29733587030
-66102890993
-63930483585
3574576099...

result:

ok 50 lines

Test #5:

score: 5
Accepted
time: 612ms
memory: 38316kb

input:

50
10000
1 2 864795802
2 3 3403898
3 4 404669874
4 5 104167086
5 6 447854285
6 7 478945838
7 8 277689928
8 9 530617846
9 10 341566235
10 11 426405663
11 12 916935917
12 13 660083740
13 14 866393523
14 15 217696996
15 16 751829899
16 17 480895442
17 18 124930746
18 19 65254843
19 20 841561751
20 21 2...

output:

-771938006413
-952145011970
-6813288531357
-1220411204311
-1298475812381
-1919630340406
-1707167565636
1223194732406
-3630699775196
-2066478342702
-4272718618922
-1865120625192
96648203485
245577835900
-1899362228818
68411064785
-725056100835
-1514985278
-241233726591
-3167720520372
-856413502472
18...

result:

ok 50 lines

Test #6:

score: 5
Accepted
time: 1154ms
memory: 76092kb

input:

20
50000
1 2 179783342
2 3 329307163
3 4 28763311
4 5 770116486
5 6 158010688
6 7 275523671
7 8 229341032
8 9 631721084
9 10 260390410
10 11 3652020
11 12 966032435
12 13 266184745
13 14 261993661
14 15 70492909
15 16 185073157
16 17 972287824
17 18 88966733
18 19 164551608
19 20 794904463
20 21 644...

output:

-4449608823265
-7460132298744
3125390209126
-8858454992059
-1331182179021
-22035288523727
-11280489810997
-7031519746696
-965629505255
-7647551004442
-8981058226914
-28023775400866
-4090460674620
-11780538861976
-15522579962636
-1476770034776
-14851945199590
-8443929185792
-2888846676635
-6037290917...

result:

ok 20 lines

Test #7:

score: 5
Accepted
time: 349ms
memory: 35828kb

input:

50
10000
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
5 40...

output:

-19633628696464
-19972167949371
-19978977724922
-19960457806556
-19898960412282
-19973399558424
-19926493255854
-19908054421275
-19902482163964
-19984448058447
-19903300687300
-19908478572948
-19981932107556
-19967569982098
-19822605774736
-19816699997242
-19980738186899
-19979700882807
-19944073444...

result:

ok 50 lines

Test #8:

score: 5
Accepted
time: 572ms
memory: 68904kb

input:

20
50000
1 2 0
2 3 0
2 4 0
3 5 0
3 6 0
4 7 0
4 8 0
5 9 0
5 10 0
6 11 0
6 12 0
7 13 0
7 14 0
8 15 0
8 16 0
9 17 0
9 18 0
10 19 0
10 20 0
11 21 0
11 22 0
12 23 0
12 24 0
13 25 0
13 26 0
14 27 0
14 28 0
15 29 0
15 30 0
16 31 0
16 32 0
17 33 0
17 34 0
18 35 0
18 36 0
19 37 0
19 38 0
20 39 0
20 40 0
21 4...

output:

-99989614381748
-99946687145289
-99865129675056
-99972360680249
-99887318868496
-99747478037808
-99984925882202
-99823114630905
-99985660996219
-99879938203299
-99941542372879
-99978008313577
-99428668939674
-99983495501272
-99931884347866
-99943955409968
-99956654218312
-99976018114299
-99952032514...

result:

ok 20 lines

Test #9:

score: 5
Accepted
time: 616ms
memory: 69652kb

input:

20
50000
1 2 0
2 3 0
3 4 0
2 5 0
2 6 0
5 7 0
2 8 0
6 9 0
8 10 0
7 11 0
7 12 0
8 13 0
11 14 0
11 15 0
4 16 0
16 17 0
12 18 0
14 19 0
8 20 0
7 21 0
19 22 0
22 23 0
14 24 0
6 25 0
22 26 0
14 27 0
25 28 0
27 29 0
5 30 0
21 31 0
30 32 0
31 33 0
9 34 0
11 35 0
2 36 0
13 37 0
8 38 0
30 39 0
36 40 0
12 41 0...

output:

-99985725110235
-99924528695125
-99946341642656
-99925574752742
-99900022970241
-99950062227901
-99980801535601
-99990784668064
-99902086800088
-99950302279692
-99968564209835
-99974658942435
-99978551916814
-99990872190677
-99974412576331
-99921837152647
-99974580050419
-99976441855815
-99975364788...

result:

ok 20 lines

Test #10:

score: 5
Accepted
time: 165ms
memory: 25380kb

input:

50
10000
1 2 424058411
2 3 364092764
3 4 649569637
4 5 107311821
5 6 589201681
6 7 837804270
7 8 477845409
8 9 622129179
9 10 815005658
10 11 882812530
11 12 954467751
12 13 528654134
13 14 423064704
14 15 883902940
15 16 241202437
16 17 311119773
17 18 260729530
18 19 471785092
19 20 943699288
20 2...

output:

-20150081524372
-19935359459085
-19991391425812
-19964303642141
-19932850212415
-20018461752434
-19898834682697
-20221127408868
-19903677164224
-19836221080562
-20145587641005
-19908956376091
-19978915091758
-20012947984620
-19866973120827
-20362005593340
-19694301832064
-19901917239424
-19869268398...

result:

ok 50 lines

Test #11:

score: 5
Accepted
time: 308ms
memory: 38952kb

input:

10092
13
1 2 376012308
2 3 872641596
2 4 969503104
3 5 493821196
3 6 412025108
1 7 712126023
6 8 245269838
2 9 50554104
9 10 452044647
4 11 24996801
6 12 999619302
3 13 243974212
13
12 9 2444221107
5 12 0
11 11 0
5 5 0
9 10 0
13 13 0
8 12 1766295001
7 7 0
8 8 0
10 10 0
12 12 0
4 11 0
2 7 0
20
1 2 85...

output:

384440443
-25595119423
-4780450131
-14969681093
-18456652728
-21505347020
6105779371
-17712338102
-440493324
-292099713
-20019099444
-25194100447
-35660658441
-4506131481
-22228045496
-5678548415
2500841277
-22303398918
-1422733793
-14598742323
-30540261882
-9262580525
-32123364738
-13283978303
-208...

result:

ok 10092 lines

Test #12:

score: 5
Accepted
time: 331ms
memory: 39400kb

input:

4921
17
1 2 532882055
2 3 812171282
2 4 78207404
4 5 114730827
5 6 808506705
4 7 333878950
7 8 775477644
7 9 848363535
7 10 821481422
10 11 357375658
11 12 99238276
12 13 895564470
13 14 682306056
2 15 665054341
6 16 223659235
16 17 471478148
17
5 6 120
6 16 0
16 17 0
11 12 213724534
3 3 0
9 9 0
8 9...

output:

-9856313382
-10800003054
-8060685665
528126548
-3967395385683
-17401875541
-9605581143
-1451946209
-27150279567
-12846547323
-30570253352
-26200749160
-4640130780
-14993957700
-27712754628
-24352330307
-26438917639
F
-17614421245
-9946318755
-8537573137
-8145086848
-25282796313
-9072193228
-13437672...

result:

ok 4921 lines

Test #13:

score: 5
Accepted
time: 626ms
memory: 34308kb

input:

50
10000
1 2 416427278
2 3 644054069
3 4 472419584
4 5 154841243
5 6 740229548
6 7 805647275
7 8 25893196
8 9 402109497
9 10 623764898
10 11 847792914
11 12 986296046
12 13 179849710
13 14 156233946
14 15 619526335
15 16 764163002
16 17 623103830
17 18 557471591
18 19 486566895
19 20 831795278
20 21...

output:

203979053899
121688688010
135924842723
20117427285
222505809403
191014230692
204005486609
104543520395
74253437803
426961709317
174640375472
38643220593
42015029520
222620461564
13867225079
41018427291
12372790475
13506942112
116801205195
72086726330
25369264533
59847581244
92281679949
20604179587
9...

result:

ok 50 lines

Test #14:

score: 5
Accepted
time: 620ms
memory: 33728kb

input:

50
10000
1 2 950613341
2 3 592354539
3 4 813579862
3 5 967703156
4 6 610563562
6 7 482990529
5 8 762382263
2 9 573202546
6 10 83067536
5 11 13525932
11 12 227298815
7 13 779836778
7 14 750761052
14 15 181469376
7 16 19494079
5 17 743988131
17 18 323746846
7 19 302470938
6 20 167831140
20 21 99446810...

output:

66606045624
31591160124
28335447831
99763890060
125045328170
14817482027
241336166201
36727477257
183955630011
360400153896
3252920970
80200634054
20945328006
113379894364
43685231850
86773801502
124055322659
190775337625
78454006503
68582744486
33330796344
119406417116
67934310087
98484719602
47724...

result:

ok 50 lines

Test #15:

score: 5
Accepted
time: 897ms
memory: 68220kb

input:

22081
21
1 2 659538900
2 3 795240945
3 4 929891954
4 5 638901861
5 6 693009757
6 7 50043084
7 8 632298292
8 9 307442678
9 10 56547981
10 11 15119139
11 12 776486541
12 13 650964235
13 14 343976304
14 15 469141843
15 16 238930900
16 17 258933808
17 18 771996708
18 19 369254864
19 20 363658288
20 21 4...

output:

5444557908
2338968606
952589049
1125338653
-540251411
1904242819
3608514594
1158484927
834530699
2164403828
749788308
-433620404
1261578335
-871534946
-573838440
251939830
-1101080962
-354567573
1252198027
2880327249
3891696567
-997656292
-101851380
5098417709
920705795
-320653430
2747965123
3581118...

result:

ok 22081 lines

Test #16:

score: 5
Accepted
time: 829ms
memory: 66140kb

input:

5216
24
1 2 220386131
2 3 622200460
3 4 441010465
4 5 944623977
4 6 311640313
6 7 467884482
6 8 358045567
6 9 743189991
4 10 189045271
10 11 847713463
10 12 439007770
10 13 156824893
7 14 236252645
14 15 675181812
15 16 762981343
15 17 329149230
9 18 399480293
18 19 447754501
19 20 735440113
9 21 69...

output:

1985614332
-63690958
9361238366
5392798027
-1618475011
622945115
2242578927
847697513
998949175
2354900796
1075197562
2310925811
7682834420
6344594239
-48660538
2965339522
1452096908
1703589050
1201385022
1133306090
2872451059
1017616339
431153934
1993689130
1477618463
3055083741
1999750451
16646672...

result:

ok 5216 lines

Test #17:

score: 5
Accepted
time: 344ms
memory: 40180kb

input:

50
10000
1 2 337289894
2 3 644529789
3 4 271847531
4 5 572013548
5 6 556451843
6 7 659023427
7 8 921127707
8 9 469405854
9 10 545997296
10 11 817609444
11 12 141992903
12 13 697921696
13 14 788063268
14 15 671026780
15 16 728175238
16 17 507914122
17 18 402265517
18 19 500627033
19 20 926252757
20 2...

output:

-19951921283710
-19824907952578
-19864270494458
-20016352146514
-19960666473367
-20014970487251
-19987572973190
-19433578048230
-19904335441647
-19973957506356
-19959015833098
-20010740988037
-20106992846250
-20061706975944
-19980712407983
-19980846575743
-19966561817887
-19903242332628
-19961317360...

result:

ok 50 lines

Test #18:

score: 5
Accepted
time: 558ms
memory: 67840kb

input:

20
50000
1 2 947441270
2 3 347862603
3 4 841221721
4 5 602718715
5 6 314169232
6 7 271568187
7 8 103308599
8 9 518351012
9 10 403259816
10 11 525661932
11 12 906706009
12 13 359328898
13 14 329646222
14 15 944812671
15 16 933960085
16 17 894441828
17 18 353503858
18 19 871801328
19 20 653054815
20 2...

output:

-99873690164108
-100044427780399
-100210304805589
-100032486879657
-100718319990423
-100939786859772
-100159592665041
-99913461299722
-99908532546244
-99939791883760
-100174857403588
-100298472920888
-100154035678345
-100345671629004
-104056010699156
-100336685783077
-102144600258598
-99980679129186...

result:

ok 20 lines

Test #19:

score: 5
Accepted
time: 520ms
memory: 67448kb

input:

15001
18
1 2 548047653
2 3 830498788
3 4 776376564
1 5 442376221
5 6 336814108
2 7 865914777
7 8 74368436
7 9 28482995
9 10 59424328
6 11 76912958
10 12 23054734
12 13 569994260
4 14 301620040
14 15 57874563
14 16 319603688
16 17 90481420
7 18 357607498
40
4 18 10432437242
2 15 9236050724
9 12 67389...

output:

-12970671591
-23241352317
-9808403356
-27271695204
-16054875604
-742765731
-9337868799
-16442064139
-27503303946
-28223798656
-36171934295
-3999115836821
-443344151
-8178261787
-7058941541
-2890049158
-10369732155
-2401898550
-12353169820
-27705609857
-21125607477
-16662785708
-23044284861
-12438811...

result:

ok 15001 lines

Test #20:

score: 5
Accepted
time: 542ms
memory: 68948kb

input:

14747
30
1 2 108495240
2 3 946632342
2 4 508027435
2 5 418511391
5 6 624220595
6 7 820640967
6 8 998707796
7 9 323081330
5 10 553410529
2 11 846772199
11 12 313696368
12 13 234001588
10 14 964945212
8 15 102994086
7 16 515192862
16 17 115268583
16 18 954140216
17 19 880753105
19 20 149105203
3 21 12...

output:

-44205106286
-24333267068
-16722424628
-20539280728
-47757682662
-28299381509
-32875981754
-14853995236
953704371
-4008588342
-28376447539
-7252406257
-8897764448
-9120231406
-41873136798
-2736844590
-10238168542
-102264284
-51777143975
-31374237538
148209214
-25744383794
-26922609666
-6069731062
15...

result:

ok 14747 lines

Extra Test:

score: 0
Extra Test Passed