Computer

Computer (树形dp)

给你一棵树，问你每个点能到达的最远距离。N<=10000。

这是道树形dp入门题（流下伤心的泪水）首先一个结点，它能到的最远点要么在子树内，要么在子树外。我们根据这个来搞dp。(dp[u][0])表示在u的子树内，u能到达的最远距离。(dp[u][1])则表示子树内的次远距离。(dp[u][2])表示u经过它的父亲的最远距离。首先(dp[u][0])和(dp[u][1])是容易求的。然后我们考虑经过父亲的情况，设u是v的父亲，那么(dp[v][2]=max(dp[u][2], dp[v][0]+w[i]==dp[u][0]?dp[u][1]:dp[u][0]))。

我还考虑了这样的情况：。我蠢蠢的认为这样子的情况，(dp[u][1])用我的代码求出来是0，是不行的。然而。。它就应该是0。因为你走了u就不能走回头路了。所以(dp[u][1])的定义不应该是u这个节点走到子树中任意一个点的的次大距离，而应该是在所有经过子节点i的最大路径中次大的哪一个。蛤蛤，真是为自己的智商感到担忧。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=10005;

class Graph{
public:
    struct Edge{
        int to, next, v; Graph *bel;
        void set(int x, int y, Graph *g){
            to=x; next=y; bel=g; }
        inline int operator *(){ return to; }
        Edge& operator ++(){
            return *this=bel->edge[next]; }
    };
    void reset(){ //edge不用清零，因为最后跳到的结点是0
        memset(fir, 0, sizeof(fir));
        cntedge=0; edge[cntedge].to=0;
    }
    void addedge(int x, int y, int w){
        edge[++cntedge].set(y, fir[x], this);
        fir[x]=cntedge; edge[cntedge].v=w;
    }
    Edge& getlink(int x){ return edge[fir[x]]; }
private:
    int cntedge, fir[maxn];
    Edge edge[maxn*2];
};

Graph g;
int n, dp[maxn][3];

void dfs1(int now, int par){
    Graph::Edge e=g.getlink(now);
    int tmp;
    for (; *e; ++e){
        if (*e==par) continue;
        dfs1(*e, now);
        tmp=dp[*e][0]+e.v;
        if (tmp>=dp[now][0]){
            dp[now][1]=dp[now][0];
            dp[now][0]=tmp;
        } else if (tmp>dp[now][1])
            dp[now][1]=tmp;
    }
}

void dfs2(int now, int par){
    Graph::Edge e=g.getlink(now);
    for (; *e; ++e){
        if (*e==par) continue;
        dp[*e][2]=max(dp[now][2],
                dp[*e][0]+e.v==dp[now][0]?
                    dp[now][1]:dp[now][0])+e.v;
        dfs2(*e, now);
    }
}

int main(){
    while (~scanf("%d", &n)){
        memset(dp, 0, sizeof(dp));
        int x, y; g.reset();
        for (int i=2; i<=n; ++i){
            scanf("%d%d", &x, &y);
            g.addedge(i, x, y); g.addedge(x, i, y);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        for (int i=1; i<=n; ++i)
            printf("%d
", max(dp[i][0], dp[i][2]));
    }
}