【DP】送你一颗圣诞树

这题…就是很毒瘤。玄学map。玄学pair。否则大点炸掉。

---

---

解

• DP。
  ans[i]为第i颗树的美观度。
  topx(nowt,x)为在第nowt颗树上所有点到x点的距离和
  disx(nowt,x,y)为在第nowt颗树上x点到y点的距离

• 关于转移：（模拟一下，分类讨论一下，得到代码）
  把当前的树拆成两个树（当初拼成它的数）然后判断各种情况，递归，记忆化搜索。虽然代码繁琐（chou）了（亿）点，但还是比较好理解的（？）
  详见代码。（万能句）

• 然后便是%%%%%%（只要我%得够标准WA就找不上我）（再%亿%同机房的增加下RP）
  %%%tjh（dalao
  %%%lth（让我扣完了标
  %%%fy（?美女快教我
  为什么你们的题解都写那么长。呆滞。

---

代码

#include <cstdio>
#include <utility>
#include <cmath>
#include <map>
#include <iostream>
#include <cstring>
#define LL long long
#define N 101
#define mod 1000000007
using namespace std;
map <pair <LL, LL>, LL> dis[N];
map <LL, LL> top[N];
LL T, m, a[N], b[N], c[N], d[N], l[N], ans[N], size[N];
LL disx(LL nowt, LL x, LL y)  //同颗树，x点走向y点
{
 if(x == y) return 0;
 if(x > y) swap(x,y);
 pair<int, int> p = make_pair (x, y);
 if(dis[nowt][p] != 0) return dis[nowt][p];  //记忆化
 if(y < size[a[nowt]]) return disx(a[nowt], x, y);  //同在第一颗树
 else if (x >= size[a[nowt]]) return disx(b[nowt], x - size[a[nowt]], y - size[a[nowt]]); 
 //同在第二颗，序号要处理下
 else
 {
  dis[nowt][p] = (disx(a[nowt], x, c[nowt]) + l[nowt]) % mod;  //依然是同下面topx函数原理差不多的操作
  dis[nowt][p] = (dis[nowt][p] + disx (b[nowt], y - size[a[nowt]], d[nowt])) % mod;
 }
 return dis[nowt][p];
}
LL topx(LL nowt, LL x)  //nowt树所有点到x的距离
{
 if(nowt == 0) return 0;
 if(top[nowt][x] != 0) return top[nowt][x];  //记忆化
 if(x < size[a[nowt]])  
 {//由于这棵树是由两颗树拼起来的，看看x在哪颗树上，这里是第一棵
  top[nowt][x] = (topx(a[nowt], x) + topx(b[nowt], d[nowt])) % mod; //第一棵树所有点走到x直接得出
  //第二棵树先走到两树连接的地方————点d[nowt]
  top[nowt][x] = (top[nowt][x] + ((l[nowt] + disx(a[nowt], c[nowt], x)) % mod) * (size[b[nowt]] % mod) % mod) % mod;
  //第二棵树的点经过连接两树的路到达第一颗树的c点，再从c点走向x点
 }
 else  //第二棵树，同上
 {
  top[nowt][x] = (topx(b[nowt], x - size[a[nowt]]) + topx(a[nowt], c[nowt])) % mod;
  top[nowt][x] = (top[nowt][x] + ((l[nowt] + disx(b[nowt], d[nowt], x - size[a[nowt]])) % mod) * (size[a[nowt]] % mod) % mod) % mod;
 }
 return top[nowt][x];
}
void work()
{
 scanf("%lld", &m);
 size[0] = 1;
 for(LL i = 1; i <= m; ++i)
 {
  scanf("%lld%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i], &l[i]);
  dis[i].clear();  //清0
  top[i].clear();
  size[i] = size[a[i]] + size[b[i]];  //合并后的树的大小
  ans[i] = (ans[a[i]] + ans[b[i]]) % mod;  //树a[i]和树b[i]内的美观度
  ans[i] = (ans[i] + (((size[a[i]] % mod) * (size[b[i]] % mod) % mod) * (l[i] % mod) % mod)) % mod;
  //两树之间交流经过多少次新路径*新路径距离
  ans[i] = (ans[i] + ((topx(a[i], c[i]) % mod) * (size[b[i]] % mod) % mod)) % mod;
  //第一颗树所有点到c[i]的距离 * b[i]的点数
  ans[i] = (ans[i] + ((topx(b[i], d[i]) % mod) * (size[a[i]] % mod) % mod)) % mod;
  //第二颗树所有点到d[i]的距离 * a[i]的点数
  printf("%lld\n", ans[i]);
 }
}
int main()
{
 scanf("%lld", &T);
 while(T--) work();
}