首页 > 代码库 > 【2016多校】T2 forest （树形DP，数论）

【2016多校】T2 forest （树形DP，数论）

2024-08-18 16:17:42   219人阅读

题意：有一棵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四个点对取最大值

        然而我懒得写了

 

  1 const mo=1000000007;
  2 var g:array[1..100000,1..2]of int64;
  3     h:array[1..100000,1..2]of longint;
  4     fa,cx,cy,b,ff:array[1..100000]of longint;
  5     f,a,ans:array[1..100000]of int64;
  6     head,vet,next:array[1..300000]of longint;
  7     n,i,x,y,tot:longint;
  8     t:int64;
  9 
 10 procedure add(a,b:longint);
 11 begin
 12  inc(tot);
 13  next[tot]:=head[a];
 14  vet[tot]:=b;
 15  head[a]:=tot;
 16 end;
 17 
 18 function max(x,y:int64):int64;
 19 begin
 20  if x>y then exit(x);
 21  exit(y);
 22 end;
 23 
 24 procedure swap(var x,y:longint);
 25 var t:longint;
 26 begin
 27  t:=x; x:=y; y:=t;
 28 end;
 29 
 30 procedure dfs(u,pre:longint);
 31 var e,v:longint;
 32 begin
 33  e:=head[u];
 34  while e<>0 do
 35  begin
 36   v:=vet[e];
 37   if v<>pre then
 38   begin
 39    ff[v]:=u;
 40    dfs(v,u);
 41   end;
 42   e:=next[e];
 43  end;
 44 end;
 45 
 46 function mi(x,y:int64):int64;
 47 var tmp:int64;
 48 begin
 49  mi:=1; tmp:=x;
 50  while y>0 do
 51  begin
 52   if y and 1=1 then mi:=mi*tmp mod mo;
 53   tmp:=tmp*tmp mod mo;
 54   y:=y>>1;
 55  end;
 56 end;
 57 
 58 function exf(x:int64):int64;
 59 begin
 60  exit(mi(x,mo-2));
 61 end;
 62 
 63 begin
 64  assign(input,‘forest.in‘); reset(input);
 65  assign(output,‘forest.out‘); rewrite(output);
 66  readln(n);
 67  for i:=1 to n do
 68  begin
 69   read(a[i]);
 70   f[i]:=a[i];
 71  end;
 72  for i:=1 to n-1 do
 73  begin
 74   read(cx[i],cy[i]);
 75   add(cx[i],cy[i]);
 76   add(cy[i],cx[i]);
 77  end;
 78  for i:=1 to n-1 do read(b[i]);
 79  dfs(1,-1);
 80  t:=1;
 81  for i:=1 to n do t:=t*a[i] mod mo;
 82  ans[n]:=t;
 83  for i:=n-1 downto 1 do
 84  begin
 85   x:=cx[b[i]]; y:=cy[b[i]];
 86   if ff[y]<>x then swap(x,y);
 87   t:=t*exf(f[y]) mod mo;
 88   fa[y]:=x;
 89   while x>0 do
 90   begin
 91    if fa[x]=0 then t:=t*exf(f[x]) mod mo;
 92    f[x]:=max(f[x],f[y]);
 93    if g[y,1]+a[y]>g[x,1] then
 94    begin
 95     if h[x,1]<>y then
 96     begin
 97      g[x,2]:=g[x,1]; h[x,2]:=h[x,1];
 98     end;
 99     g[x,1]:=g[y,1]+a[y];
100     h[x,1]:=y;
101    end
102     else if (g[y,1]+a[y]>g[x,2])and(y<>h[x,1]) then
103     begin
104      g[x,2]:=g[y,1]+a[y];
105      h[x,2]:=y;
106     end;
107    f[x]:=max(f[x],g[x,1]+g[x,2]+a[x]);
108    y:=x; x:=fa[x];
109   end;
110   t:=t*f[y] mod mo;
111   ans[i]:=t;
112  end;
113  for i:=1 to n do writeln(ans[i]);
114 
115  close(input);
116  close(output);
117 end.

 

【2016多校】T2 forest （树形DP，数论）


联系
我们