【BZOJ4472】salesman（树形DP）

题意：

给定一颗有点权的树，每个树上的节点最多能走到lim[u]次，求一条路径，使路径上的点权和最大，每个节点上的点权如果走了多次只能算一次。还要求方案是否唯一。

思路：每个点只能取lim[u]-1个子树。因为每个子树只取1次或不取，考虑树形DP,dp[u]=dp[v1]+dp[v2]+...（加lim[u]-1）个，是排序后最大的。因为不一定要去满lim[u]-1个,如果负数就不走。

判多解：

1.儿子不唯一老子不唯一。

2.取得最后一个和不取的第一个dp值相等就不唯一。

3.取得里面有0就不唯一。

 var head,vet,next,lim:array[..]of longint;

     dp,c,d,f,a:array[..]of int64;

     n,m,i,x,y,tot:longint;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 procedure swap(var x,y:int64);

 var t:int64;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var i,j:longint;

     mid:int64;

 begin

  i:=l; j:=r; mid:=c[(l+r)>>];

  repeat

   while mid<c[i] do inc(i);

   while mid>c[j] do dec(j);

   if i<=j then

   begin

    swap(c[i],c[j]); swap(d[i],d[j]);

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 procedure dfs(u,pre:longint);

 var e,v,i,m,j:longint;

 begin

  e:=head[u]; m:=;

  while e<> do

  begin

   v:=vet[e];

   if v<>pre then dfs(v,u);

   e:=next[e];

  end;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>pre then begin inc(m); c[m]:=dp[v]; d[m]:=f[v]; end;

   e:=next[e];

  end;

  if m> then qsort(,m);

  dp[u]:=a[u];

  f[u]:=; j:=;

  for i:= to m do

  begin

   if (i>lim[u]-)or(c[i]<) then break;

   inc(j);

   dp[u]:=dp[u]+c[i];

   if d[i]= then f[u]:=;

   if c[i]= then f[u]:=;

  end;

  if (j>)and(j+<=m)and(c[j]=c[j+]) then f[u]:=;

  for i:= to m do begin c[i]:=; d[i]:=; end;

 end;

 begin

  readln(n);

  for i:= to n do read(a[i]);

  lim[]:=n;

  for i:= to n do read(lim[i]);

  for i:= to n- do

  begin

   readln(x,y);

   add(x,y);

   add(y,x);

  end;

  dfs(,);

  writeln(dp[]);

  if f[]= then writeln('solution is unique')

   else writeln('solution is not unique');

 end.

巴特西

【BZOJ4472】salesman（树形DP）

最新文章

热门文章