code. compile. run. debug. share.
Source Code
Language
/// ______ __________ _____ _____ _____
/// /// \\\ ||__|| \\\ ||| ||| || || |||\\\ ///|||
/// /// \\\ ||__|| \\\ |||_____||| || || ||| \\\ /// |||
/// ///______\\\ ||__|| \\\ |||_____||| || || ||| \\\ /// |||
/// ///________\\\ ||__|| /// |||_____||| || || ||| \\\/// |||
/// /// \\\ ||__|| /// ||| ||| || || ||| |||
/// /// \\\ ||__||___/// ||| ||| ||_____|| ||| |||
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=400+5;
ll par[N][26];
vector<ll> adj[N];
ll depth[N];
bool vis[N];
ll n,q;
void dfs(ll u)
{
vis[u]=1;
for(int j=1;j<26;j++)par[u][j]=par[par[u][j-1]][j-1];
for(auto v:adj[u])
{
if(vis[v])continue;
par[v][0]=u;
depth[v]=depth[u]+1;
dfs(v);
}
}
ll get_kth(ll u,ll k)
{
ll ans=u;
while(k)
{
ll g=__lg(k);
u=par[u][g];
k-=(1LL<<g);
}
return u;
}
ll LCA(ll u,ll v)
{
if(depth[u]<depth[v])swap(u,v);
ll diff=depth[u]-depth[v];
if(diff)u=get_kth(u,diff);
if(u==v)return u;
for(ll j=25;j>=0;j--)
{
if(par[u][j]!=par[v][j])
{
u=par[u][j];
v=par[v][j];
}
}
u=par[u][0];
return u;
}
ll dist[404][404];
short dp[402][402][402];
ll m;
ll qu[404];
ll x;
ll solve(ll idx,ll mon,ll ah)
{
if(idx==m)return 1;
short &ans=dp[idx][mon][ah];
if(~ans)return ans;
ans=0;
if(dist[mon][qu[idx]]<=x)ans|=solve(idx+1,qu[idx],ah);
if(dist[ah][qu[idx]]<=x)ans|=solve(idx+1,mon,qu[idx]);
return ans;
}
void test_case()
{
cin>>n>>m;
for(int i=1;i<=n-1;i++)
{
ll u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<m;i++)cin>>qu[i];
dfs(1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ll lc=LCA(i,j);
dist[i][j]=depth[i]-depth[lc]+depth[j]-depth[lc];
}
}
ll low=1,high=n+2;
ll ans=0;
while(low<=high)
{
ll mid=(low+high)/2;
x=mid;
memset(dp,-1,sizeof dp);
short tmp=solve(0,1,1);
if(tmp)
{
ans=mid;
high=mid-1;
}
else low=mid+1;
}
cout<<ans;
}
int main()
{
FIO
// freopen("input.txt","rt",stdin);
// freopen("output.txt","wt",stdout);
int t;
t=1;
// cin>>t;
while(t--)
{
test_case();
}
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|