結果
問題 | No.2337 Equidistant |
ユーザー |
|
提出日時 | 2023-06-02 23:25:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,665 bytes |
コンパイル時間 | 2,776 ms |
コンパイル使用メモリ | 187,232 KB |
実行使用メモリ | 123,588 KB |
最終ジャッジ日時 | 2024-12-28 22:46:16 |
合計ジャッジ時間 | 15,534 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;struct ReRooting{using T = int;const T identity = 0; //mergeの演算に対する単位元int n;vector<vector<int>> G;vector<vector<T>> dp;vector<vector<T>> dp2;vector<T> ans;//vのi番目の辺の子からRを受け取ったときの処理T receive(int v, int i, T &R){return T(R);}//全体の累積lに子receiveの値をmerge//mergeの演算はモノイドでなくてはならないT merge(T l, T r){return l + r;}//親に渡すときの処理T givep(int v, T cum){return cum + 1;}ReRooting() {}ReRooting(int N):n(N){G.resize(N);dp.resize(N);dp2.resize(N);ans.resize(N,identity);}void add_edge(int a, int b) {G[a].emplace_back(b);G[b].emplace_back(a);}void read(){int a, b;for(int i = 1; i < n; i++){cin >> a >> b;a--, b--;G[a].emplace_back(b);G[b].emplace_back(a);}}void build() {for(int i = 0; i < n; i++){sort(G[i].begin(), G[i].end());}dfs(0); // 普通に木DPdfs2(0, identity); // 残りの部分木に対応するDPを計算}T dfs(int v, int p = -1) {T res = identity;int deg = G[v].size();dp[v] = vector<T>(deg, identity);for (int i = 0; i < deg; i++) {int u = G[v][i];if (u == p) continue;dp[v][i] = dfs(u, v);res = merge(res, receive(v, i, dp[v][i]) );}return givep(v,res);}void dfs2(int v, const T& dp_p, int p = -1) {int deg = G[v].size();for (int i = 0; i < deg; i++) { // 前のdfsで計算した有向辺に対応する部分木のDPを保存if (G[v][i] == p){dp[v][i] = dp_p; break;}}vector<T> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積mergefor (int i = 0; i < deg; i++) {dp_l[i + 1] = merge(dp_l[i], receive(v, i, dp[v][i]));}dp2[v] = dp_l;for (int i = deg - 1; i >= 0; i--) {dp_r[i] = merge(dp_r[i + 1], receive(v, i, dp[v][i]));}ans[v] = dp_l[deg]; // 頂点 v の答えfor (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算int u = G[v][i];if (u == p) continue;dfs2(u, givep(v,merge(dp_l[i], dp_r[i + 1])),v);}}};struct LCA_tree{int _n,MAX_LOG_V,root;vector<vector<int>> g;vector<vector<int>> parent;vector<int> depth;LCA_tree() : _n(0) {}LCA_tree(int n) : _n(n), g(n),depth(n) {MAX_LOG_V = 1;while(_n >> MAX_LOG_V) MAX_LOG_V++;parent.resize(MAX_LOG_V, vector<int>(_n));}void merge(int u, int v){g[u].push_back(v);g[v].push_back(u);}void dfs(int v,int p,int d){parent[0][v]=p;depth[v]=d;for(int i=0;i<g[v].size();i++){if(g[v][i]!=p)dfs(g[v][i],v,d+1);}}void init(int r){root=r;dfs(root,-1,0);for(int j=0;j+1<MAX_LOG_V;j++){for(int i=0;i<_n;i++){if(parent[j][i]<0)parent[j+1][i]=-1;else parent[j+1][i]=parent[j][parent[j][i]];}}}int lca(int u,int v){if(depth[u]>depth[v])swap(u,v);for(int i=0;i<MAX_LOG_V;i++){if((depth[v]-depth[u])>>i&1)v=parent[i][v];}if(u==v)return u;for(int i=MAX_LOG_V-1;i>=0;i--){if(parent[i][u]!=parent[i][v]){u=parent[i][u];v=parent[i][v];}}return parent[0][u];}//パスの辺数int dist(int u,int v){int lcav=lca(u,v);if(lcav==-1)return depth[u]+depth[v];return depth[u]+depth[v]-2*depth[lcav];}int la(int v, int k){for(int j = MAX_LOG_V - 1; j >= 0; j--){if(k >> j & 1){v = parent[j][v];}}return v;}array<int, 3> pos(int u, int v){int lcav = lca(u, v);int dv = depth[u] + depth[v] - 2 * depth[lcav];if(dv & 1) return array<int,3>({-1, -1, -1});dv /= 2;if(dv == depth[lcav] - depth[v]){return array<int,3>({lcav, la(v, dv - 1), la(u, dv - 1)});}if(depth[lcav] - depth[v] < dv) swap(v, u);return array<int,3>({lcav, la(v, dv - 1), la(v, dv + 1)});}//頂点wが頂点u,vのパス上に存在するかint on_path(int u,int v,int w){return (dist(u,w)+dist(v,w)==dist(u,v));}};int main(){ios::sync_with_stdio(false);cin.tie(0);int n, q;cin >> n >> q;vector<vector<int>> g(n);for(int i = 1; i < n; i++){int u, v;cin >> u >> v;g[--u].emplace_back(--v);g[v].emplace_back(u);}LCA_tree G1(n);ReRooting G2(n);G1.g = g;G2.G = g;G1.init(0);G2.build();auto f = [&](int v, int u){int j = lower_bound(G2.G[v].begin(), G2.G[v].end(), u) - G2.G[v].begin();return G2.dp[v][j];};while(q--){int u, v;cin >> u >> v;u--, v--;auto b = G1.pos(u, v);if(b[0] == -1){cout << 0 << '\n';continue;}int ans = n;ans -= f(b[0], b[1]) + f(b[0], b[2]);cout << ans << '\n';}}