QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#289769 | #7206. Triple | georgeyucjr | ML | 0ms | 0kb | C++23 | 12.5kb | 2023-12-23 23:34:19 | 2023-12-23 23:34:19 |
answer
#include <bits/stdc++.h>
using namespace std;
// ----------------
#if __cplusplus >= 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#define LOCAL
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define rep(i, f, t, ...) for (int i = f, ##__VA_ARGS__; i <= t; ++i)
#define red(i, f, t, ...) for (int i = f, ##__VA_ARGS__; i >= t; --i)
#define pb push_back
#define emb emplace_back
#define arr2 array<int, 2>
#define arr3 array<int, 3>
#define arr4 array<int, 4>
#define pii pair<int, int>
#define mkp make_pair
#define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)
template <class T> constexpr static T inf = numeric_limits<T>::max() / 2;
// ----------------
#ifndef LUOGU
#define auto_att __attribute__((target("avx2"), optimize("O3", "Ofast", "unroll-loop", "register", "inline")))
#else
#define auto_att
#endif
namespace fastio {
#define endl '\n'
INLINE_V static constexpr size_t buf_size = 1 << 18;
INLINE_V static constexpr size_t integer_size = 20;
INLINE_V static constexpr size_t block_size = 10000;
static char inbuf[buf_size + 1] = {};
static char outbuf[buf_size + 1] = {};
static char block_str[block_size * 4 + 1] = {};
static constexpr uint64_t power10[] = {1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000,
1000000000000,
10000000000000,
100000000000000,
1000000000000000,
10000000000000000,
100000000000000000,
1000000000000000000,
10000000000000000000u};
struct Scanner {
#ifndef LOCAL
private:
size_t pos, end;
inline void load() {
end = fread(inbuf, 1, buf_size, stdin);
inbuf[end] = '\0';
}
inline void reload() {
size_t len = end - pos;
memmove(inbuf, inbuf + pos, len);
end = len + fread(inbuf + len, 1, buf_size - len, stdin);
inbuf[end] = '\0';
pos = 0;
}
inline void skip_space() {
while (inbuf[pos] <= ' ') {
if (__builtin_expect(++pos == end, 0))
reload();
}
}
inline char get_next() { return inbuf[pos++]; }
inline char get_next_nonspace() {
skip_space();
return inbuf[pos++];
}
public:
Scanner() { load(); }
auto_att inline void read(char &c) { c = get_next_nonspace(); }
auto_att inline void read(string &s) {
skip_space();
s = "";
do {
size_t start = pos;
while (inbuf[pos] > ' ')
++pos;
s += string(inbuf + start, inbuf + pos);
if (inbuf[pos] != '\0')
break;
reload();
} while (true);
}
template <class T> typename enable_if<is_integral<T>::value, void>::type read(T &x) {
char c = get_next_nonspace();
if (__builtin_expect(pos + integer_size >= end, 0))
reload();
bool neg = false;
if (c == '-')
neg = true, x = 0;
else
x = c & 15;
while ((c = get_next()) >= '0')
x = (x << 3) + (x << 1) + (c & 15);
if (neg)
x = -x;
}
#else
template <typename _Tp> inline void read(_Tp &x) {
char ch = getchar();
int f = 1;
x = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
f = ch == '-' ? -1 : 1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ 48);
x *= f;
}
inline void read(char &c) { c = getchar(); }
inline void read(char *x) {
int i = 0;
char c = ' ';
for (; c <= ' ';)
c = getchar();
for (; c > ' ';)
x[i++] = c, c = getchar();
x[i] = 0;
}
inline void read(string &x) {
x.clear();
char c = ' ';
for (; c <= ' ';)
c = getchar();
for (; c > ' ';)
x += c, c = getchar();
}
#endif
template <class Head, class... Others> void read(Head &head, Others &...others) {
read(head);
read(others...);
}
template <class T> Scanner &operator>>(T &x) {
read(x);
return *this;
}
private:
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); }
public:
template <class T1, class T2> Scanner &operator>>(pair<T1, T2> &x) { read(x); }
};
struct Printer {
#ifndef LOCAL
private:
size_t pos = 0;
auto_att inline void flush() {
fwrite(outbuf, 1, pos, stdout);
pos = 0;
}
inline void pre_calc() {
for (size_t i = 0; i < block_size; ++i) {
size_t j = 4, k = i;
while (j--) {
block_str[i * 4 + j] = k % 10 | 48;
k /= 10;
}
}
}
static constexpr size_t get_integer_size(uint64_t n) {
if (n >= power10[10]) {
if (n >= power10[19])
return 20;
if (n >= power10[18])
return 19;
if (n >= power10[17])
return 18;
if (n >= power10[16])
return 17;
if (n >= power10[15])
return 16;
if (n >= power10[14])
return 15;
if (n >= power10[13])
return 14;
if (n >= power10[12])
return 13;
if (n >= power10[11])
return 12;
return 11;
} else {
if (n >= power10[9])
return 10;
if (n >= power10[8])
return 9;
if (n >= power10[7])
return 8;
if (n >= power10[6])
return 7;
if (n >= power10[5])
return 6;
if (n >= power10[4])
return 5;
if (n >= power10[3])
return 4;
if (n >= power10[2])
return 3;
if (n >= power10[1])
return 2;
return 1;
}
}
public:
Printer() { pre_calc(); }
~Printer() { flush(); }
inline void write(char c) {
outbuf[pos++] = c;
if (__builtin_expect(pos == buf_size, 0))
flush();
}
inline void write(const char *s) {
while (*s != 0) {
outbuf[pos++] = *s++;
// if (pos == buf_size) flush();
if (__builtin_expect(pos == buf_size, 0))
flush();
}
}
inline void write(const string &s) {
for (auto c : s) {
outbuf[pos++] = c;
// if (pos == buf_size) flush();
if (__builtin_expect(pos == buf_size, 0))
flush();
}
}
template <class T> typename enable_if<is_integral<T>::value, void>::type write(T x) {
if (__builtin_expect(pos + integer_size >= buf_size, 0))
flush();
if (x < 0)
write('-'), x = -x;
size_t digit = get_integer_size(x);
size_t len = digit;
while (len >= 4) {
len -= 4;
memcpy(outbuf + pos + len, block_str + ((x % block_size) << 2), 4);
x /= block_size;
}
memcpy(outbuf + pos, block_str + (x << 2) + (4 - len), len);
pos += digit;
}
#else
inline void write(char c) { putchar(c); }
inline void write(const char *x) {
for (int i = 0; x[i]; ++i)
write(x[i]);
}
inline void write(string s) {
for (auto c : s)
write(c);
}
template <typename _Tp> inline void write(_Tp x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 ^ 48);
}
#endif
template <class Head, class... Others> void write(const Head &head, const Others &...others) {
write(head);
write(' ');
write(others...);
}
template <class... Args> void writeln(const Args &...args) {
write(args...);
write('\n');
}
template <class T> Printer &operator<<(const T &x) {
write(x);
return *this;
}
private:
template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first, x.second); }
public:
template <class T1, class T2> Printer &operator<<(const pair<T1, T2> &x) {
write(x);
return *this;
}
};
Scanner fin;
Printer fout;
}; // namespace fastio
using fastio ::fin;
using fastio ::fout;
#define int ll
auto_att struct __QWQ__ {
int n, L, R, sm;
vector<int> a;
auto_att inline void resize(int _n) {
n = _n;
a.resize(n * 2 + 5);
}
auto_att inline void clr() { L = n, R = n - 1, sm = 0; }
auto_att inline void shift() { a[--L] = 0; }
auto_att inline int query(int p) { return p + L > R ? 0 : a[p + L]; }
auto_att inline void add(int p, int q) {
while (R < L + p)
a[++R] = 0;
a[L + p] += q, sm += q;
}
auto_att inline int querysuf(int p) {
if (L + p > R)
return 0;
int res = sm;
rep(i, 0, p - 1) res -= a[L + i];
return res;
}
};
auto_att signed main() {
int n;
auto TcaseSlvr = [&]() {
int ans = 0, big = 0, rt, Dmx = 0, tot = 0;
__QWQ__ ds;
ds.resize(n * 2 + 5);
vector<bool> vis(n + 1, false);
vector<vector<int>> G(n + 1), vec(n + 1);
vector<int> fa(n + 1, 0), mx(n + 1, 0), len(n + 1, 0), sz(n + 1, 0), heavy(n + 1, 0), cnt(n + 1, 0), L(n + 1, 0), R(n + 1, 0), U(n + 1, 0),
B(n + 1, 0);
rep(i, 1, n - 1, u, v) fin >> u >> v, G[u].pb(v), G[v].pb(u);
function<void(int, int)> dfs1 = [&](int u, int f) {
for (auto v : G[u])
if (v ^ f && !vis[v])
dfs1(v, u), sz[u] += sz[v], mx[u] = max(mx[u], sz[v]), mx[u] = max(mx[u], big - sz[u]);
if (mx[u] < mx[rt])
rt = u;
};
function<void(int, int, int, int)> dfs2 = [&](int u, int f, int bl, int dep) {
heavy[u] = -1;
if (dep > len[bl])
len[bl] = dep, vec[bl].pb(0);
++vec[bl][dep], sz[u] = 1, heavy[u] = 0;
for (auto v : G[u])
if (v ^ f && !vis[v]) {
dfs2(v, u, bl, dep + 1), sz[u] += sz[v];
if (heavy[u] == -1 || sz[v] > sz[heavy[u]])
heavy[u] = v;
}
};
function<void(int, int, int)> dfs3 = [&](int u, int f, int dep) {
ds.clr();
for (auto v : G[u])
if (v ^ f && !vis[v] && v ^ heavy[u])
dfs3(v, u, dep + 1);
if (~heavy[u])
dfs3(heavy[u], u, dep + 1), ds.shift();
function<void(int, int, int)> ins = [&](int u_, int f_, int dep_) {
++cnt[dep_], Dmx = max(dep_, Dmx);
for (auto v : G[u_])
if (v != f_ && !vis[v])
ins(v, u_, dep_ + 1);
};
for (auto v : G[u])
if (v ^ f && !vis[v] && v ^ heavy[u]) {
Dmx = 0, ins(v, u, 1);
int lst = 0, suf = ds.querysuf(Dmx + 1), pre = 0;
rep(j, 0, Dmx - dep - 1) pre += U[j];
red(j, Dmx, 1) {
int nw = ds.query(j);
ans += L[max(0ll, j - dep + 1)] * (2 * lst * nw + 2 * cnt[j] * suf);
suf += nw, ds.add(j, cnt[j]);
if (j > dep)
ans += pre * (2 * lst * nw + 2 * cnt[j] * suf), pre -= U[j - dep - 1];
lst += cnt[j], cnt[j] = 0;
}
}
ans += 2 * ds.sm * L[0], ds.add(0, 1);
};
function<void(int)> solve = [&](int u) {
tot = 0, L[0] = 1, U[0] = 1;
int mxd = 0;
for (auto v : G[u])
if (!vis[v]) {
len[v] = 0;
vec[v].pb(0);
dfs2(v, u, v, 1), B[++tot] = v, mxd = max(mxd, len[v]);
for (int d = len[v], vl = 0; ~d; --d)
(vl += vec[v][d]), L[d] += vl, U[d] += vec[v][d], R[d] += vl * (vl - 1);
}
ans += (L[1] * (L[1] - 1) - R[1]);
for (int i = 1, v; v = B[i], i <= tot; ++i) {
red(d, len[v], 0, vl = 0) L[d] -= (vl += vec[v][d]), U[d] -= vec[v][d], R[d] -= vl * (vl - 1),
ans += vec[v][d] * (L[d + 1] * (L[d + 1] - 1ll) - R[d + 1]);
dfs3(v, u, 1);
red(d, len[v], 0, vl = 0) L[d] += (vl += vec[v][d]), U[d] += vec[v][d], R[d] += vl * (vl - 1ll);
vec[v].clear();
}
fill(L.begin(), L.begin() + mxd + 1, 0);
fill(U.begin(), U.begin() + mxd + 1, 0);
fill(R.begin(), R.begin() + mxd + 1, 0);
vis[u] = true;
for (auto v : G[u])
if (!vis[v] && sz[v] > 2)
rt = 0, big = sz[v], dfs1(v, u), solve(rt);
};
rt = 0;
mx[0] = inf<int>;
big = n;
dfs1(1, 0);
solve(rt);
fout << n * (n - 1) * (n - 2) - ans << endl;
};
while(~scanf("%lld",&n)) TcaseSlvr();
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
3 1 2 2 3 4 1 2 2 3 2 4