题解 - Vijos

6

huxiuhan LV 3 @ 2008-11-18 19:43:04

算法1.

首先先说只用1次BFS求出无权无根树最长路的方法

类似拓扑排序，每次将所有度为1的点一起删除，直到最后剩下点数不超过2，那么删除的次数*2+剩下的顶点数即为这棵无根树的最长路径长度。

这么做的原理是找最长路的两端（必然在叶子节点），那么不断删除叶子节点，生成新的无根树，同样进行。

那么同样地，对于这题只要稍作改变即可。

当每轮删除度为1的点时（记得每轮是把所有度为1的点一起删除），如果它相邻的顶点度不为1，即它在新的树不是叶子节点，那么这个所删除的点必然不在最长路径上，将这些点权值赋为false，其它点为true，最后从最后剩下的点开始，对于权为true的顶点进行一次floodfill一次即可

Use this way

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 41ms

马小超 @ 2015-11-02 17:18:01

神。。。。

1

马小超 LV 8 @ 2015-11-03 13:09:09

这个题困扰了我好久好久
动规的那个方法不算太难
但是我更喜欢用dfs过他

树上的最长链的长度只需做两边dfs 这个大概都知道
现在的问题是怎么求在链上的点
因为可能有很多条所以我们还要再dfs一次

第一次dfs 随便一个点当成根求最远点
第二次dfs 用第一次求出的最远点当根求最远点这时就求出来最长链的长度
第三次dfs 用第二次求出的最远点中的任意一个当根如果某点的深度等于最长链的长度此点也在最长链上

这样就避免了最长链的两端的分支被忽视的情况

代码
type
arr=record
v,next:longint;
end;
var
t:array[0..400009] of arr;
deep,last:array[0..200009] of longint;
b:array[0..200009] of boolean; //是不是在最长链上
md,gen,tot,i,x,y,n:longint;
procedure built(x,y:longint);
begin
inc(tot);
t[tot].v:=y;
t[tot].next:=last[x];
last[x]:=tot;
end;
procedure dfs(x,d:longint); //x点的深度为d
var j,p:longint;
begin
deep[x]:=d;
j:=last[x];
while j<>0 do
begin
p:=t[j].v;
if deep[p]=0 then dfs(p,d+1);
j:=t[j].next;
end;
end;
procedure zou(x:longint); //寻找哪个点在最长链上一直向上走重复的不再走
var p,j:longint;
begin
b[x]:=true;
j:=last[x];
while j<>0 do
begin
p:=t[j].v;
if (b[p]=false) and (deep[p]<deep[x]) then zou(p);
j:=t[j].next;
end;
end;
begin
read(n);
for i:=1 to n-1 do
begin
read(x,y);
inc(x); inc(y); //编号都加1 方便处理
built(x,y);
built(y,x);
end;
dfs(1,1); //第一次dfs 我是用的1为根
for i:=1 to n do
if deep[i]>md then
begin md:=deep[i]; gen:=i; end; //找到最远点
fillchar(deep,sizeof(deep),0);
dfs(gen,1); //第二次dfs
md:=0;
for i:=1 to n do
if deep[i]>md then md:=deep[i]; //求出最长链的长度
fillchar(b,sizeof(b),false);
for i:=1 to n do //然后开始走
if deep[i]=md then zou(i);

fillchar(deep,sizeof(deep),0);
for i:=1 to n do
if deep[i]=md then gen:=i; //再寻找一个最远点当成根
dfs(gen,1); //第三次dfs
for i:=1 to n do //再走一次
if deep[i]=md then zou(i);
for i:=1 to n do //输出时序号减1
if b[i]=true then writeln(i-1);
end.

1

notblack LV 10 @ 2009-11-06 20:37:42

第300题，O(∩_∩)O哈哈~

Accepted 有效得分：100 有效耗时：632ms

我的猥琐DP…… 感觉不够快

d1[]表示以这个点为根往下的最大深度

d2[]次大

up[]通过它父亲绕过来的最大长度

d1,d2[] DFS一下就出来了

up[] 用DP来算

想DP的同学随便找个点（一般就是1号点啦），画成树状的，对于某个点，如果要它构成最长路径只有两种可能。

一：由它儿子的最大深度和次大深度构成。

二：有一条路径是从它爹上面下来

不过这有两种

（1）这个点x在它爹的最大深度路径上，up[x]=max(up[父亲]+1,d2[父亲]+1)

（2）不在它爹的最大深度路径上，up[x]=max(up[父亲]+1,d1[父亲]+1)

这两种情况，画一下图就知道了。

那么通过该点的最长路径就是max(up[x]+d1[x],d2[x]+d1[x]);

1

fjxmlhx LV 10 @ 2008-11-09 17:17:53

方法1：

首先先说只用1次BFS求出无权无根树最长路的方法。

类似拓扑排序，每次将所有度为1的点一起删除，直到最后剩下点数不超过2，那么删除的次数*2+剩下的顶点数即为这棵无根树的最长路径长度。

这么做的原理是找最长路的两端（必然在叶子节点），那么不断删除叶子节点，生成新的无根树，同样进行（也可以理解为从直径两端不断向中间伸展）。

那么，如何求在最长路上的点呢？

当每轮删除度为1的点时（记得每轮是先把所有度为1的点一起删除），如果它相邻的顶点度不为1，即它在新的树不是叶子节点，那么这个所删除的点必然不在最长路径上，将这些点权值赋为false，其它点为true，最后从最后剩下的点

开始，对于权为true的顶点进行一次floodfill一次即可。

算法正确性证明：

若一个顶点在直径内，则经过这个顶点的直径只可能是以下两种情况：

以这个顶点为根建树

1.存在多个以某儿子为根的高度最大的子树，则这些儿子都经过直径，其他儿子就会被标成false。

2.存在一个以某儿子为根的高度最大的子树，和多个以其他儿子为根的高度次大的子树，则这些儿子也都经过直径，其他点也会被标成false。

因此可以递归调用处理，也就是floodfill。

by TN

方法2：

从任意一点P出发找一个最远点Q（定理1），然后以Q为根建树，找以某儿子为根的子树中高度最大和次大的儿子，则这些儿子都为直径中的点，递归调用即可。

定理1：

最远点Q一定在直径上。

证明：

1.若P在直径上，则Q一定在直径上

2.若P不在直径上，则设直径为AB，若AB与PQ有交点，则B一定=Q;若AB与PQ无交点，PQ上某一点M到AB上某一点N(MN不经过AB和PQ中的任意一点），则MQ+MN

0

Sky1231 (sky1231) LV 10 @ 2017-11-03 12:29:55

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,l;
int R=0;
int fa[200000];
int vis[200000];
int up[200000];
int down_1[200000];
int down_2[200000];
int down_1_p[200000];
int down_2_p[200000];
vector<vector<int> > s;

void work_1(int now)
{
    vis[now]=1;
    for (int i=0;i<s[now].size();i++)
        if (vis[s[now][i]]==0)
        {
            fa[s[now][i]]=now;
            work_1(s[now][i]);
            if (down_1[now]<down_1[s[now][i]]+1)
            {
                down_2[now]=down_1[now];
                down_2_p[now]=down_1_p[now];
                down_1[now]=down_1[s[now][i]]+1;
                down_1_p[now]=s[now][i];
            }
            else if (down_2[now]<down_1[s[now][i]]+1&&down_1[s[now][i]]+1<=down_1[now])
            {
                down_2[now]=down_1[s[now][i]]+1;
                down_2_p[now]=s[now][i];
            }
        }
}

void work_2(int now)
{
    if (now!=R)
    {
        if (down_1_p[fa[now]]!=now)
            up[now]=max(up[fa[now]]+1,down_1[fa[now]]+2);
        else
            up[now]=max(up[fa[now]]+1,down_2[fa[now]]+2);
        l=max(l,up[now]);
    }
    else
        up[now]=1;
    for (int i=0;i<s[now].size();i++)
        if (s[now][i]!=fa[now])
            work_2(s[now][i]);
}

int main()
{
    while (~scanf("%d",&n))
    {
        s.clear();
        s.resize(n);
        for (int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            s[x].push_back(y);
            s[y].push_back(x);
        }
        memset(fa,0,sizeof(fa));
        memset(up,0,sizeof(up));
        memset(down_1,0,sizeof(down_1));
        memset(down_2,0,sizeof(down_2));
        memset(down_1_p,-1,sizeof(down_1_p));
        memset(down_2_p,-1,sizeof(down_2_p));
        memset(vis,0,sizeof(vis));
        work_1(R);
        l=0;
        work_2(R);
        for (int i=0;i<n;i++)
            if (up[i]+down_1[i]==l||down_1[i]+down_2[i]+1==l)
                printf("%d\n",i);
    }
}

sky1231 @ 2017-11-03 12:30:23

很H2O的題

0

feng_lingsong LV 9 @ 2016-01-24 22:35:32

简直了，一开始只加了单向边，错了好几次才发现.....
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)

using namespace std;

const int maxn = 200005;
int pool_cnt;

struct Node {
int nextNode;
Node *next;
} *N[maxn], pool[maxn << 1];

int n;

inline void AddEdge(int x, int y) {
Node *p = &pool[++pool_cnt];
*p = (Node){y, N[x]};
N[x] = p;
}
inline int read() {
int r = 0;
char p = getchar();
while (!isdigit(p)) p = getchar();
while (isdigit(p)) {r *= 10; r += (p - '0'); p = getchar();}
return r;
}
bool vis1[maxn];
int down1[maxn], down2[maxn], father[maxn];
void dfs1(int k) {
vis1[k] = true;
for (Node *p = N[k]; p; p = p->next) {
if (!vis1[p->nextNode]) {
father[p->nextNode] = k;
dfs1(p->nextNode);
if (down1[p->nextNode] + 1 > down1[k]) {
down2[k] = down1[k];
down1[k] = down1[p->nextNode] + 1;
}
else if (down1[p->nextNode] + 1 > down2[k]) down2[k] = down1[p->nextNode] + 1;
}
}
}
bool vis2[maxn];
int up[maxn];
void dfs2(int k) {
if (k != 0) {
up[k] = up[father[k]] + 1;
if (down1[father[k]] - 1 == down1[k]) up[k] = max(up[k], down2[father[k]] + 1); else up[k] = max(up[k], down1[father[k]] + 1);
}
vis2[k] = true;
for (Node *p = N[k]; p; p = p->next) {
if (!vis2[p->nextNode]) {
dfs2(p->nextNode);
}
}
}
int length[maxn];
int main(int argc, const char *argv[]) {
scanf("%d", &n);
int x, y;
rep(i, 1, n - 1) {
scanf("%d %d", &x, &y);
AddEdge(x, y);
AddEdge(y, x);
}
dfs1(0);
dfs2(0);
int maxl = 0;
rep(i, 0, n - 1) {
// printf("number:%d first:%d second:%d up:%d\n", i, down1[i], down2[i], up[i]);
length[i] = down1[i] + max(up[i], down2[i]);
maxl = max(maxl, length[i]);
}
rep(i, 0, n - 1) {
if (length[i] == maxl) printf("%d\n", i);
}
return 0;
}

0

马小超 LV 8 @ 2015-11-03 13:11:03

忘了发这个速度应该算是快的了吧楼下是我的解析

测试数据 #0: Accepted, time = 0 ms, mem = 5332 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5328 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5328 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5328 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 5328 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 5328 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 5328 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 5328 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 5332 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 5336 KiB, score = 10
Accepted, time = 341 ms, mem = 5336 KiB, score = 100

0

z55250825 LV 10 @ 2013-11-03 21:14:26

AC纪念...
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 11196 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 11192 KiB, score = 10
测试数据 #2: Accepted, time = 7 ms, mem = 11196 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 11196 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 11196 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 11192 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 11196 KiB, score = 10
测试数据 #7: Accepted, time = 265 ms, mem = 11192 KiB, score = 10
测试数据 #8: Accepted, time = 281 ms, mem = 11196 KiB, score = 10
测试数据 #9: Accepted, time = 265 ms, mem = 11196 KiB, score = 10
Accepted, time = 957 ms, mem = 11196 KiB, score = 100
咱的方法是两次dfs，求每个节点子树下的次长路，最长路，和以它为起点，向父亲走的最长路
然后每个节点的最长路就等于次长路+最长路或者最长路+向父亲走的最长路的最大值。
然后扫一遍如果该节点的最长路等于最长路输出就可以了

0

woai9bansc LV 8 @ 2012-08-28 21:33:05

我与其他的人做法大概相同，稍微改进的就是：

1、先找出这棵树的直径上的中间点，若直径的点的个数是偶数个，那么在最中间增加一个虚拟节点，设他为这个树的核心

2、然后由这个核心作为七天，DFS，如果DFS到某一个点的长度为半径，那么这条路径上的点都是符合条件的，标记一下就行了。

3、这样的好处就是不用考虑很多特殊情况，开始纠结从哪些点开始搜索浪费了很多时间，事实上从核心开始搜索是最快的！！

0

zhh1993 LV 10 @ 2009-11-07 14:22:14

Accepted 有效得分：100 有效耗时：175ms

悲剧了我的图论啊……看了题解的思路，终于弄懂floodfill的方法，调试了好久才出来(第一次用到了指针T^T)……

这个……难度1……

0

claire_ LV 10 @ 2009-10-27 10:11:09

三遍bfs，细节很多

0

1oVe YoU疾风 LV 10 @ 2009-10-22 14:23:48

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 119ms

├ 测试数据 08：答案正确... 353ms

├ 测试数据 09：答案正确... 650ms

├ 测试数据 10：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1501ms

有点慢~　~

0

和风初起 LV 3 @ 2008-11-13 20:49:00

一开始用数组总是溢出，后来经大牛提醒，原来要用指针。

唉，花了8个小时，终于AC了。

0

An-Yx LV 3 @ 2008-11-11 22:23:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：294ms

比赛时貌似也是这么写的诶

怎么重写就ac了

0

boyzkk LV 10 @ 2008-11-11 16:02:17

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 244ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：732ms

比赛时40分。。。想了很久还是不知道哪错了，结果把DFS在原模原样作一遍就AC！

0

lemon_cn LV 3 @ 2008-11-11 08:51:08

考试的时候竟然能想错......

5555555...

今天一次AC...其实不就是树网的核吗...

0

牧云海 LV 10 @ 2008-11-10 21:49:28

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：466ms

大家好像都比我快

考试时忘加递归了，20

现在一次AC

0

gamejifan LV 7 @ 2008-11-10 21:20:37

两次dp。第一次求每个点到它的叶子的最长次长路径长度，第二次把根以上的长度拿来修正这个最长次长路径，最后求出最长＋次长=l的就是

0

捕龟者x LV 6 @ 2008-11-10 20:52:50

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：356ms

0

mickey666 LV 3 @ 2008-11-10 20:37:03

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 41ms

题解

50 条题解

旅游规划(csapc)

信息

状态

开发

支持

题解

50 条题解

旅游规划(csapc)

信息

状态

开发

支持

还没有账户？

登录