【NOIP2016练习】T2 forest （树形DP，数论）

题意：有一棵N个点的树，每个点上有点权

定义路径长度为所经过的所有点的点权之和，树的直径为一棵树中最大的路径长度

有N次询问，每次询问要求回答所有树的直径之积

每次询问后会删一条边，树的数量会+1

要求回答N次询问，答案 mod 10^9+7

n<=100000

思路：因为知道每次删哪条边所以可以离线倒着做，每次加一条边

加边会使两棵树合并，考虑树的合并

已知原树的形状，可知点之间的父子关系

考虑DP，设dp[u,1],dp[u,2]为以U为根，子树中路径的最长与次长值，同时记录从哪个儿子取到

f[u]为以U为根的子树中的路径最大长度

注意最长与次长必须由两个不同的儿子转移来，更新时注意

对于ans[i]要合并X与Y，在原树中它们必定是父子关系

设X为Y的父亲

新的ANS就是旧的ans/旧的f[y]*新的f[合并后子树的根，即X的最上层根节点]

向上递归即可

出现除法取模，使用费马小定理求逆元

a^(p-2)=a^-1 (mod p)

题解方法是暴力+倍增优化，直径由U1,V1,U2,V2四个点对取最大值

然而我懒得写了

 const mo=;

 var g:array[..,..]of int64;

     h:array[..,..]of longint;

     fa,cx,cy,b,ff:array[..]of longint;

     f,a,ans:array[..]of int64;

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

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

     t:int64;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 function max(x,y:int64):int64;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

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

 end;

 procedure dfs(u,pre:longint);

 var e,v:longint;

 begin

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>pre then

   begin

    ff[v]:=u;

    dfs(v,u);

   end;

   e:=next[e];

  end;

 end;

 function mi(x,y:int64):int64;

 var tmp:int64;

 begin

  mi:=; tmp:=x;

  while y> do

  begin

   if y and = then mi:=mi*tmp mod mo;

   tmp:=tmp*tmp mod mo;

   y:=y>>;

  end;

 end;

 function exf(x:int64):int64;

 begin

  exit(mi(x,mo-));

 end;

 begin

  assign(input,'forest.in'); reset(input);

  assign(output,'forest.out'); rewrite(output);

  readln(n);

  for i:= to n do

  begin

   read(a[i]);

   f[i]:=a[i];

  end;

  for i:= to n- do

  begin

   read(cx[i],cy[i]);

   add(cx[i],cy[i]);

   add(cy[i],cx[i]);

  end;

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

  dfs(,-);

  t:=;

  for i:= to n do t:=t*a[i] mod mo;

  ans[n]:=t;

  for i:=n- downto  do

  begin

   x:=cx[b[i]]; y:=cy[b[i]];

   if ff[y]<>x then swap(x,y);

   t:=t*exf(f[y]) mod mo;

   fa[y]:=x;

   while x> do

   begin

    if fa[x]= then t:=t*exf(f[x]) mod mo;

    f[x]:=max(f[x],f[y]);

    if g[y,]+a[y]>g[x,] then

    begin

     if h[x,]<>y then

     begin

      g[x,]:=g[x,]; h[x,]:=h[x,];

     end;

     g[x,]:=g[y,]+a[y];

     h[x,]:=y;

    end

     else if (g[y,]+a[y]>g[x,])and(y<>h[x,]) then

     begin

      g[x,]:=g[y,]+a[y];

      h[x,]:=y;

     end;

    f[x]:=max(f[x],g[x,]+g[x,]+a[x]);

    y:=x; x:=fa[x];

   end;

   t:=t*f[y] mod mo;

   ans[i]:=t;

  end;

  for i:= to n do writeln(ans[i]);

  close(input);

  close(output);

 end.

巴特西

【NOIP2016练习】T2 forest （树形DP，数论）

最新文章

热门文章