結果

問題 No.2337 Equidistant
ユーザー hiro71687k
提出日時 2023-06-02 22:24:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,103 bytes
コンパイル時間 2,399 ms
コンパイル使用メモリ 210,824 KB
最終ジャッジ日時 2025-02-13 18:58:47
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll inf=2000000000000000000;
ll mod=998244353;
/* LCA(G, root): G root Lowest Common Ancestor
query(u,v): u v LCA O(logn)
: O(nlogn), O(nlogn)
*/
struct LCA {
vector<vector<long long>> parent; // parent[k][u]:= u 2^k
vector<ll> dist; // root
LCA(vector<vector<ll>> &G, ll root = 0) { init(G, root); }
//
void init(vector<vector<ll>> &G, int root = 0) {
ll V = G.size();
int K = 1;
while ((1 << K) < V) K++;
parent.assign(K, vector<ll>(V, -1));
dist.assign(V, -1);
dfs(G, root, -1, 0);
for (int k = 0; k + 1 < K; k++) {
for (int v = 0; v < V; v++) {
if (parent[k][v] < 0) {
parent[k + 1][v] = -1;
} else {
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
// 1
void dfs(vector<vector<ll>> &G, int v, int p, int d) {
parent[0][v] = p;
dist[v] = d;
for (auto e : G[v]) {
if (e != p) dfs(G, e, v, d + 1);
}
}
int query(int u, int v) {
if (dist[u] < dist[v]) swap(u, v); // u
int K = parent.size();
// LCA
for (int k = 0; k < K; k++) {
if ((dist[u] - dist[v]) >> k & 1) {
u = parent[k][u];
}
}
// LCA
if (u == v) return u;
for (int k = K - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
};
ll dfs(ll now,vector<ll>&m,vector<vector<ll>>&g){
m[now]=-1;
ll x=1;
for (ll i = 0; i < g[now].size(); i++)
{
if (m[g[now][i]]==-1)
{
continue;
}
x+=dfs(g[now][i],m,g);
}
m[now]=x;
return x;
}
int main(){
ll n,q;
cin >> n >> q;
vector<vector<ll>>g(n);
for (ll i = 0; i < n-1; i++)
{
ll a,b;
cin >> a >> b;
a--,b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<ll>m(n,0);
dfs(0,m,g);
queue<ll>que;
vector<ll>memo(n,inf);
memo[0]=0;
que.push(0);
while (!que.empty())
{
ll v=que.front();
que.pop();
for (ll i = 0; i < g[v].size(); i++)
{
if (memo[g[v][i]]>memo[v]+1)
{
memo[g[v][i]]=memo[v]+1;
que.push(g[v][i]);
}
}
}
LCA lca(g,0);
vector<ll>ans;
vector<vector<ll>>db(n,vector<ll>(30,-1));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < g[i].size(); j++)
{
if (memo[g[i][j]]==memo[i]-1)
{
db[i][0]=g[i][j];
break;
}
}
}
for (ll j = 1; j < 30; j++)
{
for (ll i = 0; i < n; i++)
{
if (db[i][j-1]==-1)
{
continue;
}
db[i][j]=db[db[i][j-1]][j-1];
}
}
vector<ll>two(40,1);
for (ll i = 1; i < 40; i++)
{
two[i]=two[i-1]*2;
}
for (ll i = 0; i < q; i++)
{
ll s,t;
cin >> s >> t;
s--,t--;
ll x=lca.query(s,t);
ll a=memo[s]-memo[x];
ll b=memo[t]-memo[x];
if (a%2!=b%2)
{
ans.push_back(0);
}else if (a==b)
{
if (a==1)
{
ans.push_back(n-m[s]-m[t]);
continue;
}
a--;
b--;
ll xx=s;
for (ll j = 0; j < 30; j++)
{
if (a&two[j])
{
xx=db[xx][j];
}
}
ll yy=t;
for (ll j = 0; j < 30; j++)
{
if (b&two[j])
{
yy=db[yy][j];
}
}
ans.push_back(n-m[xx]-m[yy]);
}else{
ll now,y;
if (a>b)
{
now=s,y=(a-b)/2;
}else{
now=t,y=(b-a)/2;
}
ll nn=now;
for (ll j = 0; j < 30; j++)
{
if (y&two[j])
{
now=db[now][j];
}
}
y--;
for (ll j = 0; j < 30; j++)
{
if (y&two[j])
{
nn=db[nn][j];
}
}
ans.push_back(m[now]-m[nn]);
}
}
for (ll i = 0; i < ans.size(); i++)
{
cout << ans[i] << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0