【JZOJ】4211 送你一棵圣诞树

Description

有$N+1$颗树，编号为$T_0$~$T_n$，对于每一棵树Ti，他在第$T_{a_i}$ 棵树的第$c_i$个点和第$T_{b_i}$ 棵树的第$d_i$个点之间连上了一条长度为$len_i$的边。在$T_i$ 中，他保持$T_{a_i}$ 中的所有节点编号不变，把$T_{b_i}$中的所有节点的编号加上$Size_{a_i}$。
我们定义一棵树的美观度为两两点之间的距离之和，现在要输出所有树的美观度。

Brute Force

我们可以模拟这个树的构成过程，然后把他们全部存下来。
对于美观度暴力遍历整棵树，加起来。

Analysis

这题其实是很隐蔽的搜索题
仔细想想，这棵树其实是之前的两棵树的组合，我们有必要知道整棵树吗？
我们只需要知道是哪颗树就行了。

我们看当前这棵树。
我们已知他的左儿子是$T_a$，右儿子是$T_b$，连接点是$x$，$y$，$Sum_a$，$Sum_b$（美观度），$Size_a$，$Size_b$（节点数），连接的边长度为蓝色那条边为$len$。
我们不妨再设$D[t][i]$表示第$t$棵树，编号为$i$的节点到整棵树的距离和。
至此，我们再结合$D[a][x]$，$D[b][y]$，我们不难推出$Sum_i$。
问题$Sum_a$，$Sum_b$是子问题，之前一定会处理过的。
那么我们剩下的问题就是$D[t][i]$怎么求了。
我们设一个状态$Dis[t][i][j]$表示树$t$里编号为$i$的点到编号$j$的点的距离。
我们可以通过$Dis[t][i][j]$来在每次合并的时候推出$D[t][i]$
$D[t][i]$就是现在的$D[t][i]$加上多出来的子树到其关键点的距离和加上$len$的其$Size$倍再加上自己到自己所在子树的关键点的距离的$Size$倍。
比较绕口但是也就这样了。

直接存下来肯定是不现实的。全部都转移也是不现实的。
怎么办？
观察发现，有效的点实质上很少。
我们用得上的$x$，$y$都是题目给出的。
我们把这些点叫为关键点。
你是不是已经知道怎么做了呢？
我们只存下关键点的相关状态。
什么叫相关状态呢？比如我这颗树把$x$标记为关键点，为了更新$x$，我们必须在之前的树里都一直维护$x$的信息，递归下去，把标记都打上，这就是这个关键点的相关状态。
我们有$N$棵树，每棵树最多标记$2*N$个点，总共只有$N*N*2$个关键点
$Dis[t][i][j]$的转移是$O(N^2)$，$D[t][i]$转移是$O(N)$
每棵树都要更新状态，总的时间复杂度是$O(N^3)$

Summary

这题非常灵活地运用了记忆化搜索的递归性质。
其实这和一些常见的最短路只存关键点状态是相似的。
只存关键点。

由于有点难理解所以我贴下代码。

#include
#include
#include
using namespace std;typedef pair PI;
typedef long long LL;const int N = 130 , Mo = 1e9 + 7;PI Bz[N][N];struct Node{int s[2];LL a,b,len,sum;
}Q[N];LL Size[N],Dis[N][N][N],D[N][N];
int n,fi[N];int Mark(int x , LL p)
{++ fi[x];if (x == 1) return fi[x];if (p > Size[Q[x].s[0]]) Bz[x][fi[x]] = PI(1 , Mark(Q[x].s[1] , p - Size[Q[x].s[0]]));else Bz[x][fi[x]] = PI(0 , Mark(Q[x].s[0] , p));return fi[x];
}void Solve()
{memset(fi , 0 , sizeof fi);scanf("%d" , &n) ; n ++;Size[1] = 1;for (int i = 2 ; i <= n ; i ++){scanf("%d%d%I64d%I64d%I64d", &Q[i].s[0], &Q[i].s[1], &Q[i].a, &Q[i].b, &Q[i].len);Q[i].len %= Mo;Q[i].s[0] ++ , Q[i].s[1] ++ , Q[i].a ++ , Q[i].b ++;Size[i] = Size[Q[i].s[0]] + Size[Q[i].s[1]]; // Size is used by MARK , we can't mod it.Q[i].a = Mark(Q[i].s[0] , Q[i].a);Q[i].b = Mark(Q[i].s[1] , Q[i].b);}for (int i = 2 ; i <= n ; i ++){Size[i] %= Mo;int lch = Q[i].s[0] , rch = Q[i].s[1] , len = Q[i].len;for (int j = 1 ; j <= fi[i] ; j ++){PI p = Bz[i][j] , p1;for (int k = 1 ; k <= fi[i] ; k ++){p1 = Bz[i][k];if (p.first == p1.first) {Dis[i][j][k] = Dis[Q[i].s[p.first]][p.second][p1.second];continue;}int b , b1;b = (!p.first) ? Q[i].a : Q[i].b;b1 = (!p1.first) ? Q[i].a : Q[i].b;Dis[i][j][k] = ((Dis[Q[i].s[p.first]][b][p.second] + Dis[Q[i].s[p1.first]][b1][p1.second]) % Mo + len ) % Mo;}}lch = Q[i].a , rch = Q[i].b;for (int j = 1 ; j <= fi[i] ; j ++){PI p = Bz[i][j];LL dis = Dis[Q[i].s[p.first]][(p.first) ? rch : lch][p.second];D[i][j] = D[Q[i].s[p.first]][p.second];D[i][j] = (D[i][j] + (D[Q[i].s[!p.first]][(p.first) ? lch : rch] + Size[Q[i].s[!p.first]] * (len + dis) % Mo) % Mo) % Mo;}lch = Q[i].s[0], rch = Q[i].s[1];Q[i].sum = D[lch][Q[i].a] * Size[rch] % Mo;(Q[i].sum += D[rch][Q[i].b]* Size[lch] % Mo) %= Mo;Q[i].sum = Q[i].sum + Size[lch] * Size[rch] % Mo * len % Mo;Q[i].sum = (Q[i].sum + Q[lch].sum) % Mo + Q[rch].sum % Mo;Q[i].sum %= Mo;printf("%I64d\n" , Q[i].sum);}
}int main()
{freopen("0.in" , "r" , stdin);freopen("0.out" , "w" , stdout);int T;scanf("%d" , &T);while (T --) Solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！