QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727292 | #8213. Graffiti | maspy | WA | 24ms | 21644kb | C++23 | 22.8kb | 2024-11-09 12:33:10 | 2024-11-09 12:33:11 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 2 "/home/maspy/compro/library/graph/base.hpp"
template <typename T>
struct Edge {
int frm, to;
T cost;
int id;
};
template <typename T = int, bool directed = false>
struct Graph {
static constexpr bool is_directed = directed;
int N, M;
using cost_type = T;
using edge_type = Edge<T>;
vector<edge_type> edges;
vector<int> indptr;
vector<edge_type> csr_edges;
vc<int> vc_deg, vc_indeg, vc_outdeg;
bool prepared;
class OutgoingEdges {
public:
OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}
const edge_type* begin() const {
if (l == r) { return 0; }
return &G->csr_edges[l];
}
const edge_type* end() const {
if (l == r) { return 0; }
return &G->csr_edges[r];
}
private:
const Graph* G;
int l, r;
};
bool is_prepared() { return prepared; }
Graph() : N(0), M(0), prepared(0) {}
Graph(int N) : N(N), M(0), prepared(0) {}
void build(int n) {
N = n, M = 0;
prepared = 0;
edges.clear();
indptr.clear();
csr_edges.clear();
vc_deg.clear();
vc_indeg.clear();
vc_outdeg.clear();
}
void add(int frm, int to, T cost = 1, int i = -1) {
assert(!prepared);
assert(0 <= frm && 0 <= to && to < N);
if (i == -1) i = M;
auto e = edge_type({frm, to, cost, i});
edges.eb(e);
++M;
}
#ifdef FASTIO
// wt, off
void read_tree(bool wt = false, int off = 1) { read_graph(N - 1, wt, off); }
void read_graph(int M, bool wt = false, int off = 1) {
for (int m = 0; m < M; ++m) {
INT(a, b);
a -= off, b -= off;
if (!wt) {
add(a, b);
} else {
T c;
read(c);
add(a, b, c);
}
}
build();
}
#endif
void build() {
assert(!prepared);
prepared = true;
indptr.assign(N + 1, 0);
for (auto&& e: edges) {
indptr[e.frm + 1]++;
if (!directed) indptr[e.to + 1]++;
}
for (int v = 0; v < N; ++v) { indptr[v + 1] += indptr[v]; }
auto counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (auto&& e: edges) {
csr_edges[counter[e.frm]++] = e;
if (!directed)
csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
}
}
OutgoingEdges operator[](int v) const {
assert(prepared);
return {this, indptr[v], indptr[v + 1]};
}
vc<int> deg_array() {
if (vc_deg.empty()) calc_deg();
return vc_deg;
}
pair<vc<int>, vc<int>> deg_array_inout() {
if (vc_indeg.empty()) calc_deg_inout();
return {vc_indeg, vc_outdeg};
}
int deg(int v) {
if (vc_deg.empty()) calc_deg();
return vc_deg[v];
}
int in_deg(int v) {
if (vc_indeg.empty()) calc_deg_inout();
return vc_indeg[v];
}
int out_deg(int v) {
if (vc_outdeg.empty()) calc_deg_inout();
return vc_outdeg[v];
}
#ifdef FASTIO
void debug() {
print("Graph");
if (!prepared) {
print("frm to cost id");
for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id);
} else {
print("indptr", indptr);
print("frm to cost id");
FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id);
}
}
#endif
vc<int> new_idx;
vc<bool> used_e;
// G における頂点 V[i] が、新しいグラフで i になるようにする
// {G, es}
// sum(deg(v)) の計算量になっていて、
// 新しいグラフの n+m より大きい可能性があるので注意
Graph<T, directed> rearrange(vc<int> V, bool keep_eid = 0) {
if (len(new_idx) != N) new_idx.assign(N, -1);
int n = len(V);
FOR(i, n) new_idx[V[i]] = i;
Graph<T, directed> G(n);
vc<int> history;
FOR(i, n) {
for (auto&& e: (*this)[V[i]]) {
if (len(used_e) <= e.id) used_e.resize(e.id + 1);
if (used_e[e.id]) continue;
int a = e.frm, b = e.to;
if (new_idx[a] != -1 && new_idx[b] != -1) {
history.eb(e.id);
used_e[e.id] = 1;
int eid = (keep_eid ? e.id : -1);
G.add(new_idx[a], new_idx[b], e.cost, eid);
}
}
}
FOR(i, n) new_idx[V[i]] = -1;
for (auto&& eid: history) used_e[eid] = 0;
G.build();
return G;
}
Graph<T, true> to_directed_tree(int root = -1) {
if (root == -1) root = 0;
assert(!is_directed && prepared && M == N - 1);
Graph<T, true> G1(N);
vc<int> par(N, -1);
auto dfs = [&](auto& dfs, int v) -> void {
for (auto& e: (*this)[v]) {
if (e.to == par[v]) continue;
par[e.to] = v, dfs(dfs, e.to);
}
};
dfs(dfs, root);
for (auto& e: edges) {
int a = e.frm, b = e.to;
if (par[a] == b) swap(a, b);
assert(par[b] == a);
G1.add(a, b, e.cost);
}
G1.build();
return G1;
}
private:
void calc_deg() {
assert(vc_deg.empty());
vc_deg.resize(N);
for (auto&& e: edges) vc_deg[e.frm]++, vc_deg[e.to]++;
}
void calc_deg_inout() {
assert(vc_indeg.empty());
vc_indeg.resize(N);
vc_outdeg.resize(N);
for (auto&& e: edges) { vc_indeg[e.to]++, vc_outdeg[e.frm]++; }
}
};
#line 4 "main.cpp"
void solve() {
LL(N);
STR(S);
Graph<int, 0> G(N);
G.read_tree();
if (len(S) == 1) return print(N);
if (len(S) == 2) {
if (S[0] == S[1])
return print(2 * (N - 1));
else {
return print((N - 1));
}
}
assert(len(S) == 3);
if (N < len(S)) return print(0);
auto AAA = [&]() -> ll {
ll ANS = 0;
FOR(v, N) {
ll d = G.deg(v);
ANS += d * (d - 1) / 2;
}
return ANS;
};
auto AAB = [&]() -> ll {
// par, me
using ARR = array<array<ll, 3>, 3>;
auto dfs = [&](auto &dfs, int v, int p) -> ARR {
vc<ARR> sub;
for (auto &e: G[v]) {
if (e.to == p) continue;
sub.eb(dfs(dfs, e.to, v));
}
ARR ANS;
FOR(i, 3) FOR(j, 3) ANS[i][j] = -infty<ll>;
FOR(par, 3) FOR(me, 3) {
if (me == 2) continue;
vc<pi> dat;
for (auto &S: sub) { dat.eb(S[me][0], S[me][1]); }
sort(all(dat), [&](auto &L, auto &R) -> bool { return L.fi - L.se > R.fi - R.se; });
// prefix==0, suffix==1
vi A0, A1;
for (auto &[a, b]: dat) A0.eb(a), A1.eb(b);
A0 = cumsum<ll>(A0);
A1 = cumsum<ll>(A1);
ll n = len(sub);
FOR(k, n + 1) {
ll ans = 0;
ans += A0[k] + (A1[n] - A1[k]);
ll a = k, b = n - k;
a += (par == 0);
b += (par == 1);
if (me == 0) ans += a * b;
chmax(ANS[par][me], ans);
}
}
return ANS;
};
auto ANS = dfs(dfs, 0, -1);
return max(ANS[2][0], ANS[2][1]);
};
auto ABA = [&]() -> ll {
using ARR = array<array<ll, 3>, 3>;
auto dfs = [&](auto &dfs, int v, int p) -> ARR {
vc<ARR> sub;
for (auto &e: G[v]) {
if (e.to == p) continue;
sub.eb(dfs(dfs, e.to, v));
}
ARR ANS;
FOR(i, 3) FOR(j, 3) ANS[i][j] = -infty<ll>;
FOR(par, 3) FOR(me, 3) {
if (me == 2) continue;
vc<pi> dat;
for (auto &S: sub) { dat.eb(S[me][0], S[me][1]); }
sort(all(dat), [&](auto &L, auto &R) -> bool { return L.fi - L.se > R.fi - R.se; });
// prefix==0, suffix==1
vi A0, A1;
for (auto &[a, b]: dat) A0.eb(a), A1.eb(b);
A0 = cumsum<ll>(A0);
A1 = cumsum<ll>(A1);
ll n = len(sub);
FOR(k, n + 1) {
ll ans = 0;
ans += A0[k] + (A1[n] - A1[k]);
ll a = k, b = n - k;
a += (par == 0);
b += (par == 1);
if (me == 1) ans += a * (a - 1); // どっち向きでもいいので!
chmax(ANS[par][me], ans);
}
}
return ANS;
};
auto ANS = dfs(dfs, 0, -1);
return max(ANS[2][0], ANS[2][1]);
};
auto ABC = [&]() -> ll {
using ARR = array<array<ll, 3>, 3>;
// [0,1,2]
auto dfs = [&](auto &dfs, int v, int p) -> ARR {
vc<ARR> sub;
for (auto &e: G[v]) {
if (e.to == p) continue;
sub.eb(dfs(dfs, e.to, v));
}
ARR ANS;
FOR(i, 3) FOR(j, 3) ANS[i][j] = -infty<ll>;
int n = len(sub);
// me == 0 or 2
{
ll ans = 0;
for (auto &x: sub) ans += max({x[0][0], x[0][1], x[0][2]});
FOR(par, 3) chmax(ANS[par][0], ans);
}
{
ll ans = 0;
for (auto &x: sub) ans += max({x[2][0], x[2][1], x[2][2]});
FOR(par, 3) chmax(ANS[par][2], ans);
}
// me == 1
sort(all(sub), [&](auto &L, auto &R) -> bool { return L[1][0] - L[1][1] > R[1][0] - R[1][1]; });
vi A0, A1;
for (auto &x: sub) A0.eb(x[1][0]), A1.eb(x[1][1]);
A0 = cumsum<ll>(A0);
A1 = cumsum<ll>(A1);
FOR(par, 3) {
FOR(k, n + 1) {
ll ans = 0;
ans += A0[k];
ans += A1[n] - A1[k];
ll d = k;
d += (par == 0);
d += (par == 2);
ll a = floor<ll>(d, 2);
ll b = ceil<ll>(d, 2);
ans += a * b;
chmax(ANS[par][1], ans);
}
}
return ANS;
};
ARR A = dfs(dfs, 0, -1);
ll ANS = 0;
FOR(k, 3) chmax(ANS, A[k][k]);
return ANS;
};
if (S[0] == S[1] && S[1] == S[2]) return print(AAA());
if (S[0] == S[1]) return print(AAB());
if (S[0] == S[2]) return print(ABA());
if (S[1] == S[2]) return print(AAB());
print(ABC());
}
signed main() { solve(); }
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
5 bob 3 2 5 1 1 4 2 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
50 abc 23 14 24 25 1 3 47 46 2 26 22 41 34 19 7 14 50 24 29 38 17 25 4 26 35 37 21 14 11 4 13 27 8 25 5 10 20 27 44 27 15 39 19 9 30 12 38 27 39 27 41 40 14 48 32 7 16 37 3 13 42 5 48 27 49 25 6 5 26 9 31 17 36 7 43 29 9 5 45 9 18 9 40 42 27 5 25 42 46 10 37 42 12 48 28 26 33 5
output:
37
result:
ok 1 number(s): "37"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
50 abc 14 26 46 47 10 13 30 19 33 46 32 50 39 6 35 13 8 5 28 3 2 21 17 22 22 6 5 20 19 3 38 3 16 2 18 34 13 6 47 6 9 28 1 2 37 47 50 10 12 34 40 19 42 19 26 46 43 3 44 47 31 47 49 18 45 34 27 13 7 34 6 34 3 45 11 44 21 13 29 24 15 40 48 39 24 6 41 47 23 27 36 21 25 21 4 20 20 44
output:
37
result:
ok 1 number(s): "37"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
50 abc 11 3 14 46 37 47 18 33 12 46 40 41 23 17 49 48 27 26 13 5 26 41 43 16 25 47 46 9 39 13 38 4 36 18 28 40 50 26 10 38 9 50 15 6 24 16 19 16 48 26 6 50 31 16 29 16 7 26 35 14 17 46 21 5 22 38 2 15 4 17 30 34 16 41 45 17 47 50 44 16 33 26 32 34 1 25 3 46 20 16 5 32 42 14 8 48 41 34
output:
44
result:
ok 1 number(s): "44"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
50 abc 9 7 43 49 26 3 14 11 17 43 23 35 19 25 44 25 2 1 10 28 4 46 21 22 15 43 39 25 16 38 38 23 34 29 47 49 46 35 5 39 25 35 32 23 27 37 3 32 37 24 20 13 33 25 1 29 30 11 31 34 18 31 50 37 13 48 22 23 8 10 41 24 42 46 36 37 48 43 49 31 40 41 12 35 24 34 45 7 35 31 7 31 11 44 28 1 6 19
output:
34
result:
ok 1 number(s): "34"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
50 abc 31 6 36 20 32 42 47 14 24 21 27 39 14 22 26 47 44 45 30 28 15 18 1 14 42 38 20 35 17 25 4 18 25 47 40 3 28 7 48 33 2 41 10 33 22 38 41 38 9 40 35 41 16 45 49 32 19 28 21 32 34 29 46 25 13 14 23 15 3 38 18 12 45 35 29 20 43 18 6 3 8 12 12 41 50 12 7 42 5 36 33 36 39 16 11 16 37 41
output:
30
result:
ok 1 number(s): "30"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
50 abc 50 18 10 32 38 18 47 13 31 6 49 18 45 47 42 4 7 18 18 27 36 13 12 13 41 12 35 8 6 40 16 8 4 22 14 44 25 2 28 18 3 27 34 32 5 27 43 5 33 11 23 24 2 18 21 39 46 5 8 49 32 19 20 28 22 12 11 5 15 38 44 7 9 5 19 49 1 16 30 50 48 25 40 11 24 27 26 5 37 50 17 24 13 5 39 26 29 27
output:
38
result:
ok 1 number(s): "38"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
51 abb 7 35 1 48 32 42 45 15 13 39 14 43 9 2 34 37 23 24 47 36 36 35 41 22 50 49 49 44 28 42 48 43 20 37 22 21 10 38 6 35 29 17 35 24 19 51 21 44 38 4 11 17 33 42 37 50 44 38 12 17 43 38 3 49 8 12 16 49 5 15 40 31 24 4 15 50 39 44 42 35 27 21 51 50 18 13 30 4 26 29 31 22 46 49 17 38 25 49 2 26
output:
54
result:
ok 1 number(s): "54"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
51 abb 4 33 29 28 44 34 31 46 46 17 27 48 25 35 45 19 36 40 35 51 22 36 43 9 26 47 21 36 12 17 51 50 13 44 3 34 19 36 15 32 47 28 1 3 2 40 33 46 5 30 48 39 41 15 8 20 14 46 34 27 40 17 24 2 38 10 9 17 30 19 32 17 16 21 23 9 42 34 6 15 10 31 11 28 18 34 49 40 37 34 50 19 28 17 39 40 20 19 7 24
output:
57
result:
ok 1 number(s): "57"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
51 abb 27 37 40 37 33 22 3 29 9 28 14 28 38 17 49 47 36 29 46 10 6 11 11 47 37 18 20 22 39 28 29 28 1 7 32 42 24 30 2 45 16 7 45 29 42 39 43 42 5 37 22 49 34 31 4 29 30 22 41 29 18 22 50 22 25 28 7 42 26 30 51 14 19 13 8 49 35 22 48 14 12 42 21 35 23 50 44 42 31 22 13 39 17 37 10 31 15 37 28 49
output:
70
result:
ok 1 number(s): "70"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
51 abb 7 43 11 39 8 5 47 44 25 49 9 30 40 3 36 17 13 41 16 50 44 10 12 7 33 44 5 2 35 7 22 45 19 43 18 32 42 19 31 10 45 29 3 19 46 48 39 2 34 25 14 43 2 19 21 7 32 16 51 27 6 24 43 41 27 32 48 15 23 43 17 16 50 43 24 28 1 13 38 19 37 19 49 2 26 10 28 43 30 19 4 22 20 42 15 19 29 44 10 19
output:
63
result:
ok 1 number(s): "63"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
51 aba 44 6 9 7 1 50 24 38 26 11 30 2 6 21 34 43 49 11 13 4 42 21 5 38 22 3 18 3 45 34 28 26 38 43 27 21 37 27 16 42 2 23 43 21 32 21 29 28 19 13 51 13 15 40 20 1 36 46 10 3 12 11 25 21 47 6 33 7 39 22 4 38 8 27 35 38 48 50 41 31 50 21 31 26 23 26 17 24 40 21 46 44 7 32 3 8 11 43 14 11
output:
132
result:
ok 1 number(s): "132"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
52 aba 19 7 11 48 4 6 5 27 46 50 6 37 50 23 12 40 37 23 13 23 32 38 22 44 52 5 34 50 26 38 35 10 51 20 7 26 41 6 15 26 39 10 10 40 3 50 33 29 30 14 45 50 14 27 21 27 42 29 49 44 31 27 18 5 36 42 16 11 29 28 24 12 8 50 38 5 43 10 48 52 1 52 47 26 40 32 2 3 44 27 28 38 20 26 23 5 17 27 9 43 25 46
output:
116
result:
ok 1 number(s): "116"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
52 aba 10 43 2 40 24 9 47 35 42 44 1 18 7 18 3 40 28 4 52 25 6 13 33 18 35 19 49 2 16 39 26 3 32 8 4 44 50 22 11 30 41 6 19 39 18 39 14 36 34 44 36 4 17 34 45 21 12 17 25 36 51 39 29 8 30 23 9 8 46 11 37 2 23 13 20 13 44 51 15 37 43 27 40 51 31 3 5 10 22 18 8 44 21 23 27 30 38 28 13 39 48 25
output:
88
result:
ok 1 number(s): "88"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
52 aba 48 38 40 22 49 23 37 3 6 12 43 42 26 22 30 39 8 7 25 7 47 41 44 11 52 1 13 1 41 14 19 41 23 39 35 13 32 19 38 13 39 41 2 27 51 21 31 19 21 9 29 36 9 39 16 27 15 22 24 42 18 30 42 9 36 30 4 7 27 9 17 5 22 9 50 30 20 16 46 52 28 21 5 16 3 1 33 22 7 28 10 21 12 34 34 39 11 39 1 11 45 11
output:
112
result:
ok 1 number(s): "112"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
52 aba 46 45 42 45 18 27 3 44 16 25 39 24 40 10 33 32 19 31 13 1 27 45 25 9 23 2 29 14 24 8 21 52 14 37 17 24 15 9 41 24 43 31 38 7 4 52 45 7 50 1 6 40 49 22 37 52 11 23 48 7 5 2 10 1 2 48 8 7 36 22 26 28 44 23 34 13 9 7 31 26 12 8 52 48 47 3 30 40 20 25 7 22 1 26 28 52 51 26 32 45 35 30
output:
106
result:
ok 1 number(s): "106"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
52 aba 36 34 23 29 28 11 2 47 33 26 16 37 27 46 52 3 8 14 44 15 51 47 37 7 34 29 50 27 12 47 6 18 20 21 17 14 18 13 10 3 49 17 13 3 42 22 30 13 46 43 5 19 9 18 11 14 38 51 21 46 40 50 39 19 48 22 43 19 24 19 19 14 22 41 45 37 15 41 26 11 31 46 4 43 35 15 3 19 41 43 32 11 29 47 1 7 47 43 7 14 25 28
output:
104
result:
ok 1 number(s): "104"
Test #21:
score: 0
Accepted
time: 20ms
memory: 20408kb
input:
300000 z 180011 260532 271217 191245 41791 255746 290587 278534 218547 277068 139010 241751 243632 263417 248223 222193 89717 215179 251082 231639 117314 8572 245286 297248 168750 266280 80957 255206 73540 12700 170796 282744 214088 139101 299056 232065 3541 39425 245901 203384 4354 21447 106700 295...
output:
300000
result:
ok 1 number(s): "300000"
Test #22:
score: 0
Accepted
time: 24ms
memory: 20116kb
input:
300000 aa 145612 276393 88541 108216 226040 100484 260244 139556 150893 213849 85295 33531 270499 248769 5250 51884 24539 76804 254304 165858 85779 118908 183955 155461 5230 80950 80213 95224 58182 122060 46066 288552 138127 46553 186220 182641 21451 14106 193341 35522 269820 212259 208311 40745 229...
output:
599998
result:
ok 1 number(s): "599998"
Test #23:
score: 0
Accepted
time: 4ms
memory: 9940kb
input:
123234 ab 5333 65911 93667 3824 117784 113995 122335 34180 100563 13017 2356 55265 68248 30680 67326 55966 55450 2923 86794 12061 49667 54440 46800 106814 4840 7419 53069 122499 34188 99215 18873 90062 115319 82268 1093 52619 108703 107429 40381 14308 91251 53870 7680 94995 90630 57256 78084 11866 3...
output:
123233
result:
ok 1 number(s): "123233"
Test #24:
score: -100
Wrong Answer
time: 21ms
memory: 21644kb
input:
300000 aaa 286864 6103 13963 130993 193857 266146 21588 192178 60950 206316 57174 172746 83177 159553 274512 266893 1479 82701 149984 220249 66444 38360 164961 269188 90561 160425 48372 223724 176008 89731 146829 119384 4625 131173 271552 74420 258647 63612 101816 202418 73996 284875 167169 62661 18...
output:
601347
result:
wrong answer 1st numbers differ - expected: '1202694', found: '601347'