結果
問題 | No.399 動的な領主 |
ユーザー | tossy |
提出日時 | 2016-08-20 13:46:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 2,324 bytes |
コンパイル時間 | 1,151 ms |
コンパイル使用メモリ | 99,944 KB |
実行使用メモリ | 22,964 KB |
最終ジャッジ日時 | 2024-04-25 10:50:26 |
合計ジャッジ時間 | 3,005 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,888 KB |
testcase_01 | AC | 3 ms
5,888 KB |
testcase_02 | AC | 3 ms
6,016 KB |
testcase_03 | AC | 2 ms
5,888 KB |
testcase_04 | AC | 4 ms
6,144 KB |
testcase_05 | AC | 10 ms
6,784 KB |
testcase_06 | AC | 118 ms
16,848 KB |
testcase_07 | AC | 119 ms
16,848 KB |
testcase_08 | AC | 110 ms
16,780 KB |
testcase_09 | AC | 112 ms
16,772 KB |
testcase_10 | AC | 4 ms
6,016 KB |
testcase_11 | AC | 8 ms
6,784 KB |
testcase_12 | AC | 82 ms
17,372 KB |
testcase_13 | AC | 81 ms
17,224 KB |
testcase_14 | AC | 59 ms
22,964 KB |
testcase_15 | AC | 68 ms
22,836 KB |
testcase_16 | AC | 72 ms
19,764 KB |
testcase_17 | AC | 108 ms
16,780 KB |
testcase_18 | AC | 115 ms
16,784 KB |
ソースコード
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <vector> #include <set> #include <map> #include <bitset> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define INF 1<<30 vector<int> tree[100010]; class LCA { private: int n,ln; // number of nodes and log n public: vector<vector<int> > parent; vector<int> depth; LCA(int _n) : n(_n), depth(_n){ ln=0; while(n>(1<<ln)) ln++; // calc log n parent = vector<vector<int> >(ln, vector<int>(n)); } void dfs(int v, int p, int d){ parent[0][v]=p; depth[v]=d; rep(i,tree[v].size()) if(tree[v][i]!=p) dfs(tree[v][i], v, d+1); } void init(int root){ dfs(root, -1, 0); for(int k=0; k+1<ln; k++){ for(int v=0; v<n; v++){ if(parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } int query(int u, int v){ if(depth[u] > depth[v]) swap(u,v); for(int k=0; k<ln; k++){ if((depth[v]-depth[u])>>k & 1) v = parent[k][v]; } // now, depth[v] == depth[u] if(u==v) return u; for(int k=ln-1; k>=0; k--){ if(parent[k][u] != parent[k][v]){ u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; // END class LCA vector<long> memo; // imos dfs, node n from f long imosTree(int n, int f){ long res=memo[n]; rep(i,tree[n].size()){ if(tree[n][i]!=f) res += imosTree(tree[n][i], n); } return memo[n]=res; } int main(){ int n, q; cin>>n; rep(i,n-1){ int u,v; scanf("%d %d", &u, &v); u--;v--; tree[u].pb(v); tree[v].pb(u); } LCA lca(n); lca.init(0); memo = vector<long>(n, 0); cin>>q; rep(i,q){ int a,b; scanf("%d %d", &a, &b); a--;b--; int p = lca.query(a,b); memo[a]++; memo[b]++; memo[p]--; if(lca.parent[0][p]!=-1) memo[lca.parent[0][p]]--; } // imos in tree imosTree(0,-1); // calc result long res=0; rep(i,n) res += (long)memo[i]*(memo[i]+1)/2; cout<<res<<endl; return 0; }