結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2019-08-28 21:37:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 2,369 bytes |
コンパイル時間 | 1,205 ms |
コンパイル使用メモリ | 108,756 KB |
実行使用メモリ | 32,848 KB |
最終ジャッジ日時 | 2024-11-15 19:12:32 |
合計ジャッジ時間 | 3,482 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <limits>#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;template<class T>class BIT {vector<T> bit;public:BIT(int n): bit(vector<T>(n+1, 0)){}T sum(int k){T ret = 0;for (++k; k > 0; k -= (k & -k)) ret += bit[k];return ret;}void add(int k, T x){for (++k; k < bit.size(); k += (k & -k)) bit[k] += x;}};class euler_tour {void dfs_sz(int v){for (auto &&u : G[v]) {if(u == par[v]) continue;par[u] = v; dep[u] = dep[v] + 1;dfs_sz(u);sub_size[v] += sub_size[u];if(sub_size[u] > sub_size[G[v][0]]) swap(u, G[v][0]);}}void dfs_hld(int v, int c, int &pos){id[v] = pos++;id_inv[id[v]]= v;tree_id[v] = c;for (auto &&u : G[v]) {if(u == par[v]) continue;head[u] = (u == G[v][0] ? head[v] : u);dfs_hld(u, c, pos);}}public:int n;vector<vector<int>> G;vector<int> par, dep, sub_size, id, id_inv, tree_id, head;explicit euler_tour(int n) : n(n), G(n), par(n), dep(n), sub_size(n, 1),id(n), id_inv(n), tree_id(n), head(n){}explicit euler_tour(vector<vector<int>> &G) :G(G), n(n), par(n), dep(n) , sub_size(n), id(n), id_inv(n), tree_id(n), head(n) {}void add_edge(int u, int v){G[u].emplace_back(v);G[v].emplace_back(u);}void build(vector<int> roots = {0}){int c = 0, pos = 0;for (auto &&i : roots) {dfs_sz(i);head[i] = i;dfs_hld(i, c++, pos);}}};int main() {int n;cin >> n;euler_tour G(n);for (int i = 1; i < n; ++i) {int x; scanf("%d", &x);G.add_edge(x, i);}G.build();ll ans = 0;BIT<ll> b(n);for (int j = n - 1; j >= 0; --j) {ans += b.sum(G.id[j]+G.sub_size[j]-1)-b.sum(G.id[j]);b.add(G.id[j], 1);}cout << ans << "\n";return 0;}