CodeForces369C On Changing Tree

昨日のCFは自分が挫折した.Aの問題を見ると、考えがあって、すぐにノックしますが、自分が長い間カウントしていない問題に苦しんでいて、多くの関数が少し思い出しました.A問題の主な方法は、各数の素因数を分解し、各素因数の個数を統計することであり、各素因数piの個数kに対して、方程式x 1+x 2+...xn=kのいくつかの非負の整数解があり、離散数学やいくつかの組合せ数学を学んだことがあるとわかりますが、答えはC(k,n+k-1)ですが、n+k-1は大きくなる可能性があるので、私は最初は小さく考えて、何度もREに貢献したので、組合せ数を計算するときに各数の階乗と対応する逆元の計算しかできません.そして各因子を算出した結果を乗せればよい.
Bの場合は書くと明らかに割れることがあるので問題はu(n),v(n),nの大きさは10^9に達するが,素数の稠密性に基づいて限られた時間内に算出することができ,10^11以内の隣接素数間隔は400以上500以上であるようで,素数の複雑さを判断するたびにルートnであるため,u(n),v(n)を大まかに見つける時間は10^7以内であり,これはCF上で绝対に计算することができて、uを知っていて、vの后ろのは简単な计算です.もちろんスピードを上げるためには、素性テストも考えられます.
Cは手に入れた時は時間があまりなくて、考えてみれば考えがついたのですが、10分では本当に打てないので、考えてみました.今日打ったばかりです.木の上で結点とその子孫を更新するのは自然にこの木をdfsシーケンスに検索するのですが、テーマのように、1層隔てて-kするのはどうしますか?2本の線分ツリーを構築することを考慮すると、まず各ツリーの深さdepを前処理し、更新するたびに1本目の線分ツリーの各ノードにx+k*dep[v]を加え、2本目の線分ツリーに-kを加える.では、尋ねるときはどうしますか.問い合わせるときの答えは,このノードの1本目の線分ツリー上の値ans 1に,2本目の線分ツリー上の値ans 2を加えて対応するノードの深さであるans 1+ans 2*dep[v]を乗じたものである.最適化できるところは実は2本建てる必要はありません.ただ1本の線分数が2つの値を維持しているだけです.私が書いたこのコードは遅いです.1.9 s、差は多くなくタイムアウトしましたが、仕方がありません.

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cmath>

#include<map>

#define maxn 300500

#define ll long long

#define mod 1000000007

using namespace std;



struct Node

{

	int l, r;

	ll add, sum;

};





struct SegmentTree

{

	Node N[4 * maxn];

	void build(int i, int L, int R)

	{

		N[i].l = L; N[i].r = R; N[i].sum = N[i].add = 0;

		if (L == R){

			return;

		}

		int M = (L + R) >> 1;

		build(i << 1, L, M);

		build(i << 1 | 1, M + 1, R);

	}



	void pushDown(int i)

	{

		ll tt = N[i].add;

		if (N[i].l == N[i].r) return;

		if (tt != 0){

			(N[i << 1].add += tt) %= mod;

			(N[i << 1 | 1].add += tt) %= mod;

			(N[i << 1].sum += (N[i << 1].r - N[i << 1].l + 1)*tt%mod) %= mod;

			(N[i << 1 | 1].sum += (N[i << 1 | 1].r - N[i << 1 | 1].l + 1)*tt%mod) %= mod;

			N[i].add = 0;

		}

	}



	void pushUp(int i)

	{

		N[i].sum = (N[i << 1].sum + N[i << 1 | 1].sum) % mod;

	}



	void add(int i, int L, int R, ll s)

	{

		if (N[i].l == L&&N[i].r == R){

			(N[i].add += s) %= mod;

			(N[i].sum += (R - L + 1)*s) %= mod;

			return;

		}

		pushDown(i);

		int M = (N[i].l + N[i].r) >> 1;

		if (R <= M) add(i << 1, L, R, s);

		else if (L > M) add(i << 1 | 1, L, R, s);

		else add(i << 1, L, M, s), add(i << 1 | 1, M + 1, R, s);

		pushUp(i);

	}

	ll query(int i, int L, int R)

	{

		if (N[i].l == L&&N[i].r == R){

			return N[i].sum;

		}

		pushDown(i);

		int M = (N[i].l + N[i].r) >> 1;

		if (R <= M) return query(i << 1, L, R);

		else if (L > M) return query(i << 1 | 1, L, R);

		else return query(i << 1, L, M) + query(i << 1 | 1, M + 1, R);

		//pushUp(i);

	}

}st[2];



int n;

vector<int> G[maxn];

int dep[maxn];

int pre[maxn];

int post[maxn];

int dfs_clock;



void dfs(int u, int fa,int d)

{

	pre[u] = ++dfs_clock;

	dep[u] = d;

	for (int i = 0; i < G[u].size(); i++){

		int v = G[u][i];

		if (v == fa) continue;

		dfs(v, u, d + 1);

	}

	post[u] = dfs_clock;

}



int main()

{

	while (cin >> n)

	{

		for (int i = 0; i <= n; i++) G[i].clear();

		int vi;

		for (int i = 2; i <= n; i++){

			scanf("%d", &vi);

			G[vi].push_back(i);

			G[i].push_back(vi);

		}

		dfs_clock = 0;

		dfs(1, -1, 0);

		st[0].build(1, 1, n); st[1].build(1, 1, n);

		int q; scanf("%d", &q);

		ll vq, xq, kq;

		int tq;

		for (int i = 0; i < q; i++){

			scanf("%d", &tq);

			if (tq == 1){

				scanf("%I64d%I64d%I64d", &vq, &xq, &kq);

				st[0].add(1, pre[vq], post[vq], (xq + dep[vq] * kq)%mod);

				st[1].add(1, pre[vq], post[vq], -kq);

			}

			else{

				ll ans = 0; scanf("%d", &vq);

				ans = (ans + st[0].query(1, pre[vq], pre[vq])) % mod;

				ans = (ans + st[1].query(1, pre[vq], pre[vq])*dep[vq]) % mod;

				ans = (ans + mod) % mod;

				printf("%I64d
", ans);

			}

		}

	}

	return 0;

}