首页 > 代码库 > [CF592D]Super M
[CF592D]Super M
题目大意：
给定一颗n个节点树，边权为1，树上有m个点被标记，问从树上一个点出发，经过所有被标记的点的最短路程，以及可行的最小的端点编号。（起终点自选）
M<=N<=123456
思路：
随便定一个标记节点为根，然后以该节点开始遍历，将不是标记节点的叶节点剪掉，剩下的边数为P。求出树的直径L。答案即为2*P-L。
另外注意一定要保证节点编号最小。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<algorithm> 5 inline int getint() { 6 int ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^‘0‘; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘);10 return x;11 }12 const int N=123457,inf=0x7fffffff;13 int n,m;14 bool a[N]={0};15 struct Edge {16 int to;17 bool cut;18 };19 std::vector<Edge> e[N];20 inline void add_edge(const int u,const int v) {21 e[u].push_back((Edge){v,false});22 e[v].push_back((Edge){u,false});23 }24 int u=inf,x=inf,v=inf,l=0;25 void find_u(const int x,const int parent,const int depth) {26 if(depth>l) {27 l=depth;28 u=x;29 }30 else if(depth==l) {31 u=std::min(u,x);32 }33 for(unsigned int i=0;i<e[x].size();i++) {34 if(e[x][i].to==parent||e[x][i].cut) continue;35 find_u(e[x][i].to,x,depth+1);36 }37 }38 void find_v(const int x,const int parent,const int depth) {39 if(depth>l) {40 l=depth;41 v=x;42 }43 else if(depth==l) {44 v=std::min(v,x);45 }46 for(unsigned int i=0;i<e[x].size();i++) {47 if(e[x][i].to==parent||e[x][i].cut) continue;48 find_v(e[x][i].to,x,depth+1);49 }50 }51 bool cut(const int x,const int parent) {52 bool ret=true;53 for(unsigned int i=0;i<e[x].size();i++) {54 if(e[x][i].to==parent) continue;55 if(cut(e[x][i].to,x)) {56 e[x][i].cut=true;57 n--;58 }59 else {60 ret=false;61 }62 }63 return ret&&!a[x];64 }65 int main() {66 n=getint()-1,m=getint();67 for(int i=0;i<n;i++) add_edge(getint(),getint());68 int x=inf;69 for(int i=0;i<m;i++) {70 int t=getint();71 a[t]=true;72 x=std::min(x,t);73 }74 cut(x,0);75 find_u(x,0,0);76 find_v(u,0,0);77 printf("%d\n%d\n",std::min(u,v),(n<<1)-l);78 return 0;79 }
[CF592D]Super M
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。