50 条题解

  • 6
    @ 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

  • 1
    @ 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
    @ 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
    @ 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
    @ 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);
        }
    }
    
  • 0
    @ 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
    @ 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
    @ 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
    @ 2012-08-28 21:33:05

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

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

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

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

  • 0
    @ 2009-11-07 14:22:14

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

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

    这个……难度1……

  • 0
    @ 2009-10-27 10:11:09

    三遍bfs,细节很多

  • 0
    @ 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
    @ 2008-11-13 20:49:00

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

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

  • 0
    @ 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
    @ 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
    @ 2008-11-11 08:51:08

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

    5555555...

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

  • 0
    @ 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
    @ 2008-11-10 21:20:37

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

  • 0
    @ 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
    @ 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

信息

ID
1476
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
684
已通过
149
通过率
22%
被复制
2
上传者