HDU5764 After a Sleepless Night 树形乱搞题

分析（官方题解）：

假设根已确定，可以发现新树若合法，需满足以下性质：根节点是n；儿子的值不大于父亲；具有相同值的节点形成一条链，并且链不会发生“分叉”（即有多个最低点）。所以对于新树中有出现的值x，原树在新树x链的最低点应为x，而其他新值为x的点，原值应小于x。那么我们先将所有链的最低点放上对应值，而空着的点和还没用的值进行配对。贪心使答案字典序最小：从大到小枚举未用的值，用大根堆维护该值可以填入的位置id，取最大id填入。(否则，若某一步的值a匹配了非最大id x，而最大id y在后面配了值b，那么交换xy将产生更优解)。还有一种方法是从大到小枚举空位置，填入最接近小于该位置新值的未用的值。这用set是容易实现的。并且队友想出了使用并查集+双向链表的写法，可做到并查集复杂度(O(n*a(n)))。不合法的情况除了不满足上述性质，还有就是匹配的过程中出现值或位置不够用。

然后考虑根的选择。由上所述，根的值一定是新树n链的两个端点之一。可以发现，无论选哪个做根，不影响其它链的上下方向及链之间的相对关系，即不影响合法性。因为没选的那一头一定填n，所以我们贪心地选择id小的端点做根（否则交换两个端点的值，将得到更优的答案）。当然也可以两个点都跑一遍。（出题人写hint的时候，把自己绕晕了。不好意思。）

一点感想：这个题就是说原树是有根树（每个点有权值），新树每个节点的权值是其子树的最大值

由于是排列(也就是每个权值都不一样)，所以只有链状，具体的分析见这一篇

http://blog.csdn.net/bblss123/article/details/52058959

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

typedef  long long LL;

const int N = 1e5+;

int head[N],tot;

struct Edge{

  int v,next;

}edge[N<<];

void add(int u,int v){

   edge[tot].v=v;

   edge[tot].next=head[u];

   head[u]=tot++;

}

int val[N],ret[N],d[N],n,T,color[N],fa[N],kase;

vector<int>s;

bool can[N];

bool dfs(int u){

  int sp=;

  for(int i=head[u];~i;i=edge[i].next){

     int v=edge[i].v;

     if(v==fa[u])continue;

     if(val[v]>val[u])return false;

     else if(val[v]==val[u]){if((++sp)>)return false;}

     fa[v]=u;

     if(!dfs(v))return false;

  }

  if(!sp){color[val[u]]=u;ret[u]=val[u];can[val[u]]=false;}

  return true;

}

bool solve(){

   s.clear();scanf("%d",&n);tot=;

   for(int i=;i<=n;++i)color[i]=head[i]=-,fa[i]=d[i]=,can[i]=true;

   for(int i=;i<=n;++i){

    scanf("%d",&val[i]);

    if(val[i]==n)s.push_back(i);

   }

   for(int i=;i<n;++i){

      int u,v;scanf("%d%d",&u,&v);

      add(u,v);add(v,u);

      if(val[u]==n&&val[v]==n)++d[u],++d[v];

   }

   if(!s.size())return false;

   for(int i=;i<s.size();++i)

     if(d[s[i]]<d[s[]]||d[s[i]]==d[s[]]&&s[i]<s[])

        swap(s[i],s[]);

   if(d[s[]]>)return false;

   if(!dfs(s[]))return false;

   priority_queue<int>q;

   for(int i=n;i>;--i){

     if(can[i]){

        if(q.empty())return false;

        ret[q.top()]=i;q.pop();

     }

     if(color[i]!=-){

        int tmp=color[i];

        while(val[fa[tmp]]==i){

           q.push(fa[tmp]);

           tmp=fa[tmp];

        }

     }

   }

  return true;

}

int main(){

  scanf("%d",&T);

  while(T--){

    printf("Case #%d:",++kase);

    if(!solve())printf(" Impossible\n");

    else {

      for(int i=;i<=n;++i)printf(" %d",ret[i]);

      printf("\n");

    }

  }

  return ;

}

巴特西

HDU5764 After a Sleepless Night 树形乱搞题

最新文章

热门文章