Submission #6516950
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define ALLR(a) (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void debug(vector<vector<ll>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
void debug(vector<ll>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}
//m.emplace(x,0).fi->second++;
template< typename G >
struct DoublingLowestCommonAncestor {
const ll LOG;
vector< ll > dep;
const G &g;
vector< vector< ll > > table;
DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
table.assign(LOG, vector< ll >(g.size(), -1));
}
void dfs(ll idx, ll par, ll d) {
table[0][idx] = par;
dep[idx] = d;
for(auto &to : g[idx]) {
if(to != par) dfs(to, idx, d + 1);
}
}
void build() {
dfs(0, -1, 0);
for(ll k = 0; k + 1 < LOG; k++) {
for(ll i = 0; i < table[k].size(); i++) {
if(table[k][i] == -1) table[k + 1][i] = -1;
else table[k + 1][i] = table[k][table[k][i]];
}
}
}
ll query(ll u, ll v) {
if(dep[u] > dep[v]) swap(u, v);
for(ll i = LOG - 1; i >= 0; i--) {
if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
}
if(u == v) return u;
for(ll i = LOG - 1; i >= 0; i--) {
if(table[i][u] != table[i][v]) {
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
}
};
int main(){
ll i,j,o;
ll res=0,res1=INF,res2=-INF,buf=0;
bool judge = true;
ll n;cin>>n;
vector<vector<ll>>listg(n);
for(i=0;i<n-1;i++){
ll p,q;cin>>p>>q;
listg[p-1].push_back(q-1);
listg[q-1].push_back(p-1);
}
DoublingLowestCommonAncestor<
vector<vector<ll>>>tree(listg);
tree.build();
ll q;cin>>q;
vector<ll>a(q),b(q);
for(i=0;i<q;i++)cin>>a[i]>>b[i];
for(i=0;i<q;i++){
a[i]--;b[i]--;
ll len=tree.dep[a[i]]+tree.dep[b[i]];
len-=tree.dep[tree.query(a[i],b[i])]*2;
cout<<len+1<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
tute7627 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3147 Byte |
Status |
AC |
Exec Time |
387 ms |
Memory |
27632 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
78 ms |
23408 KB |
subtask1_02.txt |
AC |
78 ms |
23536 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
384 KB |
subtask1_06.txt |
AC |
2 ms |
384 KB |
subtask1_07.txt |
AC |
92 ms |
21248 KB |
subtask1_08.txt |
AC |
96 ms |
21120 KB |
subtask1_09.txt |
AC |
94 ms |
21120 KB |
subtask1_10.txt |
AC |
98 ms |
21120 KB |
subtask1_11.txt |
AC |
98 ms |
21120 KB |
subtask1_12.txt |
AC |
97 ms |
21120 KB |
subtask2_01.txt |
AC |
285 ms |
27632 KB |
subtask2_02.txt |
AC |
282 ms |
25584 KB |
subtask2_03.txt |
AC |
192 ms |
2048 KB |
subtask2_04.txt |
AC |
193 ms |
2048 KB |
subtask2_05.txt |
AC |
211 ms |
2304 KB |
subtask2_06.txt |
AC |
206 ms |
2304 KB |
subtask2_07.txt |
AC |
368 ms |
22256 KB |
subtask2_08.txt |
AC |
368 ms |
22256 KB |
subtask2_09.txt |
AC |
387 ms |
22256 KB |
subtask2_10.txt |
AC |
385 ms |
22256 KB |
subtask2_11.txt |
AC |
378 ms |
22256 KB |
subtask2_12.txt |
AC |
385 ms |
22256 KB |