| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 122975 | davitmarg | Mousetrap (CEOI17_mousetrap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n,trap,m,u[100005],nxt[100005],dp[100005],d[100005],ans;
vector<int> g[100005],t[100005];
void maketree(int v)
{
u[v]=1;
if(v==trap)
{
nxt[v]=1;
return;
}
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(u[to])
continue;
t[v].PB(to);
maketree(to);
if(nxt[to])
{
dp[v]+=dp[to];
nxt[v]=1;
}
}
dp[v]+=t[v].size()-1;
dp[v]*=nxt[v];
}
void dfs(int v,int p=0,int last=1,int sum=0)
{
d[v]=d[p]+1;
if(nxt[v])
{
last=v;
sum=0;
}
else if(!t[v].empty())
sum+=t[v].size()-1;
for(int i=0;i<t[v].size();i++)
{
int to=t[v][i];
dfs(to,v,last,sum);
}
if(t[v].empty() && !nxt[v])
{
ans=max(ans,dp[last]+sum-1+d[v]-d[last]);
ans=max(d[v]+d[trap]-d[last]);
}
}
int main()
{
cin>>n>>trap>>m;
for(int i=1;i<=n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].PB(b);
g[b].PB(a);
}
maketree(m);
d[0]=-1;
dfs(m);
cout<<ans<<endl;
return 0;
}
/*
5 2 5
1 2
2 3
3 4
4 5
*/