题目

解析

\(Code\)

#include<cstdio>

#include<map>

#include<iostream>

#include<cstring>

using namespace std;

typedef unsigned long long LL;

const int N = 70;

const LL P = 1e9 + 7;

map<pair<LL , pair<LL , LL> > , LL> vis_to;

map<pair<LL , LL> , LL> vis_all;

struct node{

	LL a , b , c , d , l , sz , f;

}q[N];

inline LL get(LL x , LL u , LL v)

{

	if (q[x].sz == 1 || u == v) return 0;

	if (vis_to[make_pair(x , make_pair(u , v))]) return vis_to[make_pair(x , make_pair(u , v))];

	LL res = 0 , a = q[x].a , b = q[x].b , c = q[x].c , d = q[x].d , l = q[x].l , sz = q[a].sz;

	if (u > v) swap(u , v);

	if (v <= sz) res = get(a , u , v);

	else if (u > sz) res = get(b , u - sz , v - sz);

	else res = (get(a , u , c) + l + get(b , v - sz , d)) % P;

	vis_to[make_pair(x , make_pair(u , v))] = res;

	return res;

}

inline LL all(LL x , LL u)

{

	if (q[x].sz == 1) return 0;

	if (vis_all[make_pair(x , u)]) return vis_all[make_pair(x , u)];

	LL res = 0 , a = q[x].a , b = q[x].b , c = q[x].c , d = q[x].d , l = q[x].l , sz = q[a].sz;

	if (u <= sz) res = ((all(a , u) + all(b , d)) % P + q[b].sz % P * ((l + get(a , u , c)) % P) % P) % P;

	else res = ((all(b , u - sz) + all(a , c)) % P + q[a].sz % P * ((l + get(b , u - sz , d)) % P) % P) % P;

	vis_all[make_pair(x , u)] = res;

	return res;

}

int main()

{

	int T;

	scanf("%d" , &T);

	for(; T; T--)

	{

		vis_to.clear() , vis_all.clear();

		int n;

		scanf("%d" , &n);

		memset(q , 0 , sizeof q);

		q[0] = node{0 , 0 , 0 , 0 , 0 , 1};

		LL a , b , c , d , l;

		for(register int i = 1; i <= n; i++)

		{

			scanf("%lld%lld%lld%lld%lld" , &a , &b , &c , &d , &l);

			++c , ++d;

			q[i] = node{a , b , c , d , l , q[a].sz + q[b].sz};

			q[i].f = ((q[a].f + q[b].f) % P + q[a].sz % P * all(b , d) % P

				+ q[b].sz % P * all(a , c) % P + q[a].sz % P * (q[b].sz % P) % P * l % P) % P;

			printf("%lld\n" , q[i].f);

		}

	}

}
巴特西

JZOJ 4211. 【五校联考1day2】送你一颗圣诞树

题目

解析

\(Code\)

最新文章

热门文章
