結果
問題 | No.2337 Equidistant |
ユーザー |
|
提出日時 | 2023-06-02 23:02:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,881 bytes |
コンパイル時間 | 4,336 ms |
コンパイル使用メモリ | 239,860 KB |
実行使用メモリ | 111,968 KB |
最終ジャッジ日時 | 2024-12-28 21:36:51 |
合計ジャッジ時間 | 20,665 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 WA * 24 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,b) for(int i=0;i<b;i++)#define rrep(i,b) for(int i=b-1;i>=0;i--)#define rep1(i,b) for(int i=1;i<b;i++)#define repx(i,x,b) for(int i=x;i<b;i++)#define rrepx(i,x,b) for(int i=b-1;i>=x;i--)#define fore(i,a) for(auto& i:a)#define rng(x) (x).begin(), (x).end()#define rrng(x) (x).rbegin(), (x).rend()#define sz(x) ((int)(x).size())#define pb push_back#define fi first#define se second#define pcnt __builtin_popcountllusing namespace std;using namespace atcoder;using ll = long long;using ld = long double;template<typename T> using mpq = priority_queue<T, vector<T>, greater<T>>;template<typename T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<typename T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<typename T> ll sumv(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}bool yn(bool a) { if(a) {cout << "Yes" << endl; return true;} else {cout << "No" << endl; return false;}}#define dame { cout << "No" << endl; return;}#define dame1 { cout << -1 << endl; return;}#define cout2(x,y) cout << x << " " << y << endl;#define coutp(p) cout << p.fi << " " << p.se << endl;#define out cout << ans << endl;#define outd cout << fixed << setprecision(20) << ans << endl;#define outm cout << ans.val() << endl;#define outv fore(yans , ans) cout << yans << "\n";#define outdv fore(yans , ans) cout << yans.val() << "\n";#define coutv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}#define coutv2(v) fore(vy , v) cout << vy << "\n";#define coutvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define coutvm2(v) fore(vy , v) cout << vy.val() << "\n";using pll = pair<ll,ll>;using pil = pair<int,ll>;using pli = pair<ll,int>;using pii = pair<int,int>;using pdd = pair<ld,ld>;using vi = vector<int>;using vd = vector<ld>;using vl = vector<ll>;using vs = vector<string>;using vb = vector<bool>;using vpii = vector<pii>;using vpli = vector<pli>;using vpll = vector<pll>;using vpil = vector<pil>;using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvs = vector<vector<string>>;using vvb = vector<vector<bool>>;using vvpii = vector<vector<pii>>;using vvpli = vector<vector<pli>>;using vvpll = vector<vpll>;using vvpil = vector<vpil>;using mint = modint998244353;//using mint = modint1000000007;//using mint = dynamic_modint<0>;using vm = vector<mint>;using vvm = vector<vector<mint>>;vector<int> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};ll gcd(ll a, ll b) { return a?gcd(b%a,a):b;}ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}#define yes {cout <<"Yes"<<endl;}#define yesr { cout <<"Yes"<<endl; return;}#define no {cout <<"No"<<endl;}#define nor { cout <<"No"<<endl; return;}const double eps = 1e-10;const ll LINF = 1001002003004005006ll;const int INF = 1001001001;#ifdef MY_LOCAL_DEBUG#define show(x) cerr<<#x<<" = "<<x<<endl#define showp(p) cerr<<#p<<" = "<<p.fi<<" : "<<p.se<<endl#define show2(x,y) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<endl#define show3(x,y,z) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<endl#define show4(x,y,z,x2) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<" : "<<#x2<<" = "<<x2<<endl#define test(x) cout << "test" << x << endl#define showv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}#define showv2(v) fore(vy , v) cout << vy << "\n";#define showvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define showvm2(v) fore(vy , v) cout << vy.val() << "\n";#else#define show(x)#define showp(p)#define show2(x,y)#define show3(x,y,z)#define show4(x,y,z,x2)#define test(x)#define showv(v)#define showv2(v)#define showvm(v)#define showvm2(v)#endiftemplate<typename T>struct LCA {int n, root, l;vector<vector<int>> to;vector<vector<T>> co;vector<int> dep;vector<T> costs;vector<vector<int>> par;LCA(int n):n(n),to(n),co(n),dep(n),costs(n) {l = 0;while ((1<<l) < n) ++l;par = vector<vector<int>>(n+1,vector<int>(l,n));}void add_edge(int a, int b, T c=1) {to[a].push_back(b); co[a].push_back(c);to[b].push_back(a); co[b].push_back(c);}// par[x][0],dep,costsを計算void _dfs(int v, int d=0, T c=0, int p=-1) {if (p != -1) par[v][0] = p;dep[v] = d;costs[v] = c;for (int i = 0; i < sz(to[v]); ++i) {int u = to[v][i];if (u == p) continue;_dfs(u, d+1, c+co[v][i], v);}}void init(int _root=0) {root = _root;_dfs(root);for (int i = 0; i < l-1; ++i) {for (int v = 0; v < n; ++v) {par[v][i+1] = par[par[v][i]][i];}}}int lca(int a,int b){if (dep[a] > dep[b]) swap(a,b);int gap = dep[b]-dep[a];for (int i = l-1; i >= 0; --i) {int len = 1<<i;if (gap >= len) {gap -= len;b = par[b][i];}}if (a == b) return a;for (int i = l-1; i >= 0; --i) {int na = par[a][i];int nb = par[b][i];if (na != nb) a = na, b = nb;}return par[a][0];}int getPar(int x,int k){int now = x;rrep(i,30){if ((k >> i & 1) == 1){now = par[now][i];}}return now;}int length(int a, int b) {int c = lca(a,b);return dep[a]+dep[b]-dep[c]*2;}T dist(int a, int b) {int c = lca(a,b);return costs[a]+costs[b]-costs[c]*2;}};// 初期化方法 LCA<T> g(n) : nは頂点数、Tはコストのタイプ、注) 宣言 → add_edge → init の順で呼び出す// add_edge(a,b,c) : a,b間にコストcの辺をはる。cは省略可(1となる)。// init() : ダブリングにより各頂点の2^i個上の親を計算。結果はpar[v][i]に入る。// lca(a,b) : 頂点a,bのlcaを出力。// getPar(x,k) : 頂点xの2^k上の祖先を出力。// length(a,b) : 頂点a,b間の辺の数を出力。// dist(a,b) : 頂点a,b間のコストを出力。void solve(){int n,q; cin>>n>>q;vvi e(n);LCA<int> l(n);rep(i,n-1){int a,b; cin>>a>>b;a--; b--;e[a].pb(b);e[b].pb(a);l.add_edge(a,b);}l.init();// vvi q_center(n);vvpii q_ver(n);vl ans(q,n);rep(i,q){int s,t; cin>>s>>t;s--; t--;int x;ll d = l.dist(s,t);if (d%2==1){ans[i] = 0;continue;}d /= 2;if (l.dep[s]>l.dep[t]){x = l.getPar(s,d);}else{x = l.getPar(t,d);}q_ver[s].pb({i,x});q_ver[t].pb({i,x});// q_center[x].pb(i);}vvi query(n);auto dfs = [&](auto dfs,int x,int pre)->int{int sum = 0;vi sub = query[x];query[x].clear();fore(y , q_ver[x]){query[y.se].pb(y.fi);}fore(y , e[x]){if(y == pre) continue;int r = dfs(dfs ,y ,x);sum += r;fore(y , query[x]){ans[y] -= r;}query[x].clear();}sum++;fore(y , sub){ans[y] -= (n-sum);}return sum;};dfs(dfs,0,-1);outv;return;}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin>>t;rep(i,t){solve();}return 0;}