【题解】Luogu P3629 [APIO2010] 巡逻

建立第二条边$(u,v)$后,会形成新的环

若两环不重合,则$(u,v)$间的路径只需走一次,答案更优

若两环重合,还需将第二个环与建立新的道路相结合,重合部分由只需走一次变成不得不走两次

所以

$k=1$时,两遍$dfs$求树的直径,链接直径($L1$)的两端,答案为$2*(n-1)-L1+1$

$k=2$时,把直径($L1$)上的边权取反,再求一遍直径($L2$),答案即为$2*n-L1-L2$

code

【题解】Luogu P3629 [APIO2010] 巡逻
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 namespace gengyf{
 4 #define ll long long
 5 const int mod=1e5+3;
 6 const int maxn=1e5+10;
 7 inline int read(){
 8     int x=0,f=1;
 9     char c=getchar();
10     while(c<0||c>9){if(c==-)f=-1;c=getchar();}
11     while(c>=0&&c<=9){x=(x*10)+c-0;c=getchar();}
12     return x*f;
13 }
14 int n,k,d[maxn],fa[maxn];bool vis[maxn];
15 struct edge{
16     int nxt,to,w;
17 }e[maxn<<1];
18 int head[maxn],cnt=1,ans;
19 inline void add(int from,int to,int w){
20     e[++cnt].to=to;e[cnt].nxt=head[from];
21     e[cnt].w=w;head[from]=cnt;
22 }
23 void dfs(int x,int &rt){
24     vis[x]=1;
25     for(int i=head[x];i;i=e[i].nxt){
26         if(vis[e[i].to])continue;
27         d[e[i].to]=d[x]+1;
28         if(d[e[i].to]>=d[rt])rt=e[i].to;
29         fa[e[i].to]=i;dfs(e[i].to,rt);
30     }
31     vis[x]=0;
32 }
33 void dp(int x,int &root){
34     vis[x]=1;
35     for(int i=head[x];i;i=e[i].nxt){
36         if(vis[e[i].to])continue;
37         dp(e[i].to,root);
38         root=max(root,d[x]+d[e[i].to]+e[i].w);
39         d[x]=max(d[x],d[e[i].to]+e[i].w);
40     }
41 }
42 int main(){
43     n=read();k=read();
44     for(int i=1;i<n;i++){
45         int u,v;
46         u=read();v=read();
47         add(u,v,1);add(v,u,1);
48     }
49     int rt=1;
50     dfs(1,rt);
51     d[rt]=fa[rt]=0;
52     int root=rt;
53     dfs(rt,root);
54     ans=((n-1)<<1)-d[root]+1;
55     if(k==2){
56         while(fa[root]){
57             e[fa[root]].w=-1;e[fa[root]^1].w=-1;
58             root=e[fa[root]^1].to;
59         }
60         root=0;
61         memset(d,0,sizeof(d));
62         dp(rt,root);
63         ans-=root-1;
64     }
65     printf("%d",ans);
66     return 0;
67 }
68 }
69 signed main(){
70   gengyf::main();
71   return 0;
72 }
View Code

 

【题解】Luogu P3629 [APIO2010] 巡逻

上一篇:Winform中设置ZedGraph的曲线符号Symbol以及对应关系


下一篇:window10关闭多任务中的时间轴