hdu4607 Park Visit 解题报告

Tyyyyyy · 2021-07-22 20:11:30 · 个人记录

原题

核心思想：从特殊到一般的推导。

首先得到题目给出的是一棵树。

先来考虑走完所有景点的情况：显然，要让走的路程最小，n个点会被分为两个部分：一条链和该链的分叉。

链上的部分只用走一次，分叉部分则需要走两次。因此，要使走的路程最短，这个链显然就是树的直径。

所以，假设树上的边权和为sum，直径长度为d。

当走完所有景点，即k=n时：ans=2*sum-d。

接下来我们来考虑走n-1个点的情况。

要少走一个点，这个点要么在直径上，要么在直径的分叉上。

在直径上少走一个点，总的路程会比之前少1，而在分叉上少走一个点，总的路程会少2。

所以类比以上情况，我们可以得到以下（不知道算不算贪心）的贪心算法：

只要能在分叉上少走，则在分叉上少走；否则在直径上少走。

显然，对于一棵边权和为sum，直径为d且每条边边权都为1的树（即为题目给出的树），设分叉数量为num，则：

因此，我们得到以下通项公式：

当需要经过k个点，即少走n-k个点时：

设需要经过的最短路程为l，则：

代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,a,b,c,tot,h[100010];
int dist[100010],id,maxd,sum;
struct node
{
    int v,w,nxt;
}e[200010];
void add(int u,int v,int w)
{
    ++tot;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nxt=h[u];
    h[u]=tot;
}
void dfs(int u,int fa,int dis)//求直径
{
    dist[u]=dis;
    for(int i=h[u];i;i=e[i].nxt)
    {
        if(e[i].v==fa)continue;
        dfs(e[i].v,u,dis+e[i].w);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        tot=maxd=sum=0;
        memset(h,0,sizeof(h));
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            sum++;
            add(a,b,1);
            add(b,a,1);
        }
        dfs(1,0,0);
        for(int i=1;i<=n;i++)
        {
            if(maxd<dist[i])maxd=dist[i],id=i;
        }
        dfs(id,0,0);
        maxd=0;
        for(int i=1;i<=n;i++)maxd=max(maxd,dist[i]);
        int L=2*sum-maxd;
        int fc=sum-maxd;
        while(m--)
        {
            int k;
            scanf("%d",&k);
            if(n-k<=fc)printf("%d\n",2*sum-maxd-2*(n-k));
            else printf("%d\n",maxd-(n-k-fc));
        }
    }
    return 0;   
}