APIO2010巡逻（树上带权直径）
标签：http ted roo 而且 问题 can scanf main amp
题目链接：https://www.luogu.org/problem/show?pid=3629
题解：
看到这题题解一片空白，身为蒟蒻的我也想为社会做点贡献……
首先要知道：
1.假如不加边，每条边都要走两次。
2.假如加了一条边，那么会形成一个环，而且环上的边只需要走一次，其余的边要走两次。
（自己yy以下就可以知道了）
对于k=1的话，我们就要使环上的边尽量多，也就是说我们要找树的直径，使得树的直径在环内。
而对于k=2的话，再加一条边的时候，会再多一个环。
这时我们要知道：
1.如果一条边仅在第二个环出现过，只用走一次。
2.如果一条边在两个环都出现过，要走两次。
3.如果一条边在两个环都没出现过，要走两次。
（自己yy以下就可以知道了）
所以我们给第一个环上的边-1的权值，其余边给1的权值，求出树上权值最大的一条路径（假直径O(∩_∩)O）
然后问题就迎刃而解了。
附上蒟蒻的代码，我的100来行，同一机房神犇的代码60+行
#include
#include
#include
#include
#include
#include
#includeusing namespace std;
int n,k,root1,root2,cir,cir2;
int cur,head[100010],d[100010],heavy[100010],w[100010];
struct tedge
{
int to,nex;
}e[200010];
struct data
{
int e,v;
}son[100010];
void Add(int u,int v)
{
cur++;
e[cur].to = v;
e[cur].nex = head[u];
head[u] = cur;
}
bool cmp(data a,data b)
{
return a.e>b.e;
}
void dfs(int u,int f)
{
int cnts=0;
for (int i=head[u]; i!=-1; i=e[i].nex)
{
int v=e[i].to;
if (v==f) continue;
dfs(v,u);
if (d[u]w[v])
{
d[u] = d[v]+w[v];
heavy[u] = v;
}
}
for (int i=head[u]; i!=-1; i=e[i].nex)
{
int v=e[i].to;
if (v==f) continue;
cnts++; son[cnts].e = d[v]+w[v]; son[cnts].v = v;
}
sort(son+1,son+1+cnts,cmp);
if (cnts==0) d[u] = 0;
if (cnts>=1&&cir1].e)
{
cir = son[1].e;
root1 = son[1].v;
}
if (cnts>=2&&cir1].e+son[2].e)
{
cir = son[1].e+son[2].e;
root1 = son[1].v; root2 = son[2].v;
}
}
void Change()
{
int u = root1;
while (u!=0)
{
w[u] = -1; u = heavy[u];
}
u = root2;
while (u!=0)
{
w[u] = -1; u = heavy[u];
}
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=0; i)
head[i] = -1;
for (int i=2; i)
w[i] = 1;
for (int i=1; i)
{
int x,y;
scanf("%d%d",&x,&y);
Add(x,y); Add(y,x);
}
cir = 0;
dfs(1,0);
if (k==1)
{
printf("%d\n",2*(n-1)-cir+1);
return 0;
}
Change();
cir2 = cir; cir = -1e9;
for (int i=1; i)
d[i] = -1e9;
dfs(1,0);
printf("%d\n",2*(n-1)-cir-cir2+2);
return 0;
}
APIO2010巡逻（树上带权直径）
标签：http ted roo 而且 问题 can scanf main amp
原文地址：http://www.cnblogs.com/Janous/p/7526024.html
评论