#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2000555
int n,t,m,fa[SZ],f[SZ]; Edg
vector<int> so[1000555];
void dfs(int x)
{
for esb(x,e,b)
if(b!=fa[x]) fa[b]=x,so[x].pb(b),dfs(b);
}
bool sp[SZ];
void dp(int x)
{
if(x==m)
{
f[x]=0;
return;
}
for esb(x,e,b)
if(b!=fa[x]) dp(b);
vector<ll> ss;
for esb(x,e,b)
if(b!=fa[x])
{
if(!sp[b])
ss.pb(f[b]+1+so[x].size()-1-sp[x]); //???
else
ss.pb(f[b]);
}
sort(ss.begin(),ss.end(),greater<ll>());
if(ss.size()==0) f[x]=0;
else if(ss.size()==1) f[x]=!sp[x];
else f[x]=ss[1];
if(sp[x]) f[x]-=so[x].size()-1;
// cout<<x<<"w"<<f[x]<<"\n";
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
adde(a,b);
}
dfs(t);
ll ans=0;
if(t==m)
{
puts("0");
return 0;
}
for(int j=m;;j=fa[j])
{
sp[j]=1;
if(j!=m)
ans+=so[j].size()-1;
if(j==t) break;
}
// cerr<<"CA:"<<ans<<"\n";
dp(t); ans+=f[t];
printf("%lld\n",ans);
}
Compilation message
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&t);
~~~~~^~~~~~~~~~~~~~~~~~~
mousetrap.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23808 KB |
Output is correct |
2 |
Correct |
25 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
24056 KB |
Output is correct |
4 |
Incorrect |
24 ms |
23808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
516 ms |
66904 KB |
Output is correct |
2 |
Correct |
505 ms |
62636 KB |
Output is correct |
3 |
Correct |
1501 ms |
67576 KB |
Output is correct |
4 |
Correct |
618 ms |
45944 KB |
Output is correct |
5 |
Correct |
1456 ms |
67608 KB |
Output is correct |
6 |
Correct |
1485 ms |
67692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23808 KB |
Output is correct |
2 |
Correct |
25 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
24056 KB |
Output is correct |
4 |
Incorrect |
24 ms |
23808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23808 KB |
Output is correct |
2 |
Correct |
25 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
24056 KB |
Output is correct |
4 |
Incorrect |
24 ms |
23808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |