关于刚才的比赛 D 题

题目总版

@[zimujunqwq](/user/118196) ```cpp #include <bits/stdc++.h> using namespace std; #define x first #define y second #define db double #define ll long long #define iinf 0x3f3f3f3f #define linf 0x3f3f3f3f3f3f3f3f #define sz(a) (int)((a).size()) #define ba(a) (a).begin(),(a).end() #define R(i,n) for(int i=0;i<(n);++i) #define L(i,n) for(int i=(n)-1;i>=0;--i) //Main using myt=function<void(int,int)>; int& mymin(int &x,int y){return x=x<y?x:y;} //Main//Function int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n,k; cin>>n>>k; vector<vector<int>> adj(n); R(i,n-1){ int u,v; cin>>u>>v,--u,--v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> imp(n); R(i,k){ int u; cin>>u,--u; imp[u]=true; } myt pushup=[&](int u,int fa){ for(int v:adj[u])if(v!=fa) pushup(v,u),imp[u]|=imp[v]; }; pushup(0,-1); vector<vector<int>> f(n); vector<int> siz(n); myt dp=[&](int u,int fa){ siz[u]=1,f[u].assign(1,0); for(int v:adj[u])if(v!=fa){ if(!imp[v]) continue; dp(v,u),siz[u]+=siz[v]; vector<int> g=f[u]; f[u].assign(siz[u],siz[u]-1); R(i,siz[u]-siz[v])R(j,siz[v]){ if(j==0){ mymin(f[u][i+f[v][j]+1],g[i]); mymin(f[u][i],g[i]+f[v][j]+1); } else { mymin(f[u][i+f[v][j]+1],g[i]+j+1); mymin(f[u][i+j+1],g[i]+f[v][j]+1); } } R(i,siz[u]-1) mymin(f[u][i+1],f[u][i]); } }; dp(0,-1); int ns=iinf; R(i,n+1) mymin(ns,max(i,f[0][i])); cout<<ns*2<<'\n'; return 0; } ```
by George1123 @ 2021-01-16 18:44:26


@[George1123](/user/118365) 感谢王队/qq
by zimujun @ 2021-01-16 19:11:03


|