Hdu 2196 Computer (树的直径或树形DP)

小咪咪 2022-08-27 03:53 220阅读 0赞

貌似这题是树形DP的经典题，树形DP着实不熟，先用树的直径做下，具体解法见代码注释，后面附的测试数据是discuss里的。

树形DP解法可以参考：http://www.cnblogs.com/andre0506/archive/2012/10/11/2719429.html

题意：有很多机器通过一棵树连在一起，每条边有一个权值，求每个机器到离他最远的机器的距离。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=40005;
    
    struct Node
    {
    	int v,w;
    	int next;
    }edges[N];
    
    int n,m,e;
    int head[N],dis[N],d1[N],d2[N];
    bool vis[N];
    
    void Add (int u,int v,int w)
    {
    	edges[e].v=v;
    	edges[e].w=w;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int BFS (int u)
    {
        int root=u;
    	memset(vis,false,sizeof(vis));
    	memset(dis,0,sizeof(dis));
    	queue<int> Q;
    	Q.push(u);
    	vis[u] = true;
    	while (!Q.empty())
    	{
    		int s=Q.front();
    		Q.pop();
    		for (int i=head[s];i!=-1;i=edges[i].next)
    		{
    			int v=edges[i].v;
    			if (vis[v]==false)
    			{
    				dis[v]=dis[s]+edges[i].w;
    				Q.push(v);
    				vis[v]=true;
    				if (dis[v]>dis[root])
    					root=v;
    			}
    		}
    	}
    	return root;
    }
    
    int main ()
    {
    	while (~scanf("%d",&n))
    	{
    		memset(head,-1,sizeof(head));
    		memset(d1,0,sizeof(d1));
    		memset(d2,0,sizeof(d2));
    		int u,w;
    		e=0;
    		int i;
    		for (i=2;i<=n;i++)
    		{
    			scanf("%d%d",&u,&w);
    			Add(i,u,w);
    			Add(u,i,w);
    		}
    		int far=BFS(1); //先从任意点BFS一次
    		far=BFS(far); //从最长路的一个端点BFS一次
    		for (i=1;i<=n;i++)
                d1[i]=dis[i];
            BFS(far); //再从最长路的另一个端点BFS一次
    		for (i=1;i<=n;i++)
                d2[i]=dis[i];
            for (i=1;i<=n;i++)
                printf("%d\n",max(d1[i],d2[i]));
    	}
    	return 0;
    }
    /*
    In:
    16
    1 1
    2 1
    2 1
    2 1
    2 1
    3 1
    4 1
    4 1
    6 1
    6 1
    7 1
    7 1
    8 1
    10 1
    14 1
    
    Out:
    5
    4
    5
    4
    5
    5
    6
    5
    5
    6
    6
    7
    7
    6
    7
    7*/