Submission #7466359
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 lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
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>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T 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;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}
template<typename T>
void debug(vector<vector<T>>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;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
struct LCA{
ll datasize = 21;
ll n,root;//rootを根とする頂点数nの根付き木
vector<ll>depth;//0から
vector<vector<ll>>G,data;
LCA(vector<vector<ll>>g,ll r):G(g),n(g.size()),root(r){
data.assign(n,vector<ll>(datasize,-1));
depth.assign(n,-1LL);
build();
}
void build(){
dfs(root,0);
for(ll i=1;i<datasize;i++){
for(ll j=0;j<n;j++){
if(data[j][i-1]==-1)data[j][i]=-1;
else data[j][i]=data[data[j][i-1]][i-1];
}
}
}
void dfs(ll k,ll d){
depth[k]=d;
for(ll i=0;i<G[k].size();i++){
if(depth[G[k][i]]==-1){
data[G[k][i]][0]=k;
dfs(G[k][i],d+1);
}
}
}
ll deep(ll x){
return x>=0?depth[x]:-1;
}
ll query(ll x,ll y){
if(depth[x]<depth[y])swap(x,y);
ll tmp = datasize - 1;
while(depth[x]!=depth[y]){
while(tmp>=1&&depth[y]>=deep(data[x][tmp]))tmp--;
x = data[x][tmp];
}
tmp = datasize - 1;
while(x!=y){
while(tmp>=1&&data[x][tmp]==data[y][tmp])tmp--;
x = data[x][tmp];
y = data[y][tmp];
}
return x;
}
};
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
ll res=0,res1=INF,res2=-INF,buf=0;
bool judge = true;
ll n;cin>>n;
vector<vector<ll>>g(n);
for(ll i=0;i<n-1;i++){
ll p,q;
cin>>p>>q;
g[p-1].push_back(q-1);
g[q-1].push_back(p-1);
}
struct LCA lca(g,0);
ll q;cin>>q;
rep(i,0,q){
ll a,b;cin>>a>>b;
a--;b--;
ll x=lca.query(a,b);
cout<<lca.deep(a)+lca.deep(b)-2*lca.deep(x)+1<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
tute7627 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3579 Byte |
Status |
AC |
Exec Time |
343 ms |
Memory |
40448 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 |
72 ms |
40448 KB |
subtask1_02.txt |
AC |
72 ms |
40448 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
640 KB |
subtask1_06.txt |
AC |
2 ms |
640 KB |
subtask1_07.txt |
AC |
94 ms |
38144 KB |
subtask1_08.txt |
AC |
97 ms |
37888 KB |
subtask1_09.txt |
AC |
95 ms |
37760 KB |
subtask1_10.txt |
AC |
105 ms |
37760 KB |
subtask1_11.txt |
AC |
107 ms |
37760 KB |
subtask1_12.txt |
AC |
98 ms |
37760 KB |
subtask2_01.txt |
AC |
248 ms |
40448 KB |
subtask2_02.txt |
AC |
252 ms |
40448 KB |
subtask2_03.txt |
AC |
171 ms |
512 KB |
subtask2_04.txt |
AC |
175 ms |
512 KB |
subtask2_05.txt |
AC |
184 ms |
896 KB |
subtask2_06.txt |
AC |
187 ms |
1024 KB |
subtask2_07.txt |
AC |
290 ms |
38144 KB |
subtask2_08.txt |
AC |
301 ms |
37888 KB |
subtask2_09.txt |
AC |
312 ms |
37760 KB |
subtask2_10.txt |
AC |
322 ms |
37760 KB |
subtask2_11.txt |
AC |
343 ms |
37760 KB |
subtask2_12.txt |
AC |
342 ms |
37760 KB |