文章目录

• • 题面
  • 题解

题面

传送门

小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。
这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，
其中 fi <i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其
中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。
每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可
以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力
将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。
除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。
现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

题解

题意
给定 N N N 个节点，以 1 1 1 为根的有根树，每个节点 u u u 有个防御值 h p [ u ] hp[u] hp[u] ，除根节点外，节点还有特效 { a , b } \{a,b\} {a,b}，再给 M M M 个士兵所在节点位置，

有血量 a r r [ i ] arr[i] arr[i]​，这 M M M​ 个士兵往根方向走，能够进入 u u u​ 的条件是， a r r [ i ] > = h p [ u ] arr[i]>=hp[u] arr[i]>=hp[u]​ ，否则，则止步于 u u u​，也就是在 u u u​ 死亡。进入之后，节点特效 { a , b } \{a,b\} {a,b}，当 a = = 1 a==1 a==1时，士兵血量 a r r [ i ] ∗ = b arr[i]*=b arr[i]∗=b， a = = 0 a==0 a==0时， a r r [ i ] + = b arr[i]+=b arr[i]+=b

要求， N N N个节点重每个节点 u u u有多少个士兵止步于 u u u​， M M M 个士兵，每个士兵能够进入多少个节点

分析

考虑，在某个节点 v v v​ 时，所有能够进入（ v v v​儿子节点）的士兵，都要尝试进入 v v v​，此时把所有能够进入儿子节点的士兵都加进来，根据条件，计算哪些能够真正的进入节点 v v v​，从而解决进入节点 v v v的问题。
计算过程，士兵血量小的，肯定最先死亡，止步于 v v v，因此可以对于每一个子树，维护一个小顶堆

如何快速维护子树堆合并后的节点信息呢？尝试用左偏树解决。
左偏树能够在 log ⁡ ( n ) \log(n) log(n) 的复杂度合并两个最小堆。
但是，如何解决进入后，对堆里面的所有节点进行更新呢？

左偏树恰好也能像线段树一样，支持懒惰延迟修改。
此时，也就只是维护一个，乘法和加法了。线段树基操，大概就是先乘后加。
如果士兵在某个节点被小顶堆弹出了，那么就die了，记录die 位置的深度
同时节点的 c n t [ u ] + + cnt[u]++ cnt[u]++，记录死亡的个数
士兵进入的节点个数 n u m = d e p [ s t ] − d e p [ d i e ] num = dep[st] - dep[die] num=dep[st]−dep[die]，st为士兵初始位置的深度

//322971H 
/*
  @Author: YooQ
*/
#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define ll long long
#define int long long
#define FILE_OUT freopen("out", "w", stdout);
#define FILE_IN freopen("in", "r", stdin);
#define debug(x) cout << #x << ": " << x << "\n";
#define AC 0
#define WA 1
#define INF 0x3f3f3f3f
const ll MAX_N = 1e6+5;
const ll MOD = 1e9+7;
int N, M, K;

int head[MAX_N];
int tot = 0;
struct Edge{
	int to, nxt;
}edge[MAX_N];


void addEdge(int u, int v) {
	edge[tot].nxt = head[u];
	edge[tot].to = v;
	head[u] = tot++;
}

int hp[MAX_N];
int arr[MAX_N];
int brr[MAX_N];

struct Tr {
	int k, id, l, r, dis, add, mul, lazy;
}tr[MAX_N];

int root[MAX_N];
int indx = 0;

int mk(int k, int id) {
	tr[++indx] = {k, id, 0, 0, 0, 0, 1, 0};
	return indx;
}

void calc(int rt, int add, int mul) {
	if (!rt) return;
	tr[rt].k = tr[rt].k * mul + add;
	tr[rt].add = tr[rt].add * mul + add;
	tr[rt].mul = tr[rt].mul * mul;
	tr[rt].lazy = 1;
}

void push_up(int rt) {
	tr[rt].dis = tr[tr[rt].r].dis + 1;
}

void push_down(int rt) {
	if (!tr[rt].lazy) return;
	calc(tr[rt].l, tr[rt].add, tr[rt].mul);
	calc(tr[rt].r, tr[rt].add, tr[rt].mul);
	tr[rt].add = 0;
	tr[rt].mul = 1;
	tr[rt].lazy = 0;
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	push_down(x);push_down(y);
	if (tr[x].k > tr[y].k) swap(x, y);
	tr[x].r = merge(tr[x].r, y);
	if (tr[tr[x].r].dis > tr[tr[x].l].dis) swap(tr[x].l, tr[x].r);
	push_up(x);
	return x;
}

void pop(int &rt) {
	push_down(rt);
	rt = merge(tr[rt].l, tr[rt].r);
}

int top(int rt) {
	push_down(rt);
	return tr[rt].k;
}

int dep[MAX_N];
int st[MAX_N];
int die[MAX_N];
int cnt[MAX_N];

void dfs(int u, int d) {
	dep[u] = d;
	int v;
	for (int i = head[u];~i;i=edge[i].nxt) {
		dfs(v = edge[i].to, d+1);
		if (root[v]) root[u] = merge(root[u], root[v]);
	}
	while (root[u] && top(root[u]) < hp[u]) {
		++cnt[u];
		die[tr[root[u]].id] = d;
		pop(root[u]);
	}
	if (arr[u]) {
		calc(root[u], 0, brr[u]);
	} else {
		calc(root[u], brr[u], 1);
	}
}

void init() {
	memset(head, -1, sizeof head);
	tot = 0;
	indx = 0;
}

void solve(){
	init();
	sc("%lld%lld", &N, &M);
	for (int i = 1; i <= N; ++i) {
		sc("%lld", &hp[i]);
	}
	int u, v;
	for (int i = 2; i <= N; ++i) {
		sc("%lld%lld%lld", &u, &arr[i], &brr[i]);
		addEdge(u, i);
	}
	for (int i = 1; i <= M; ++i) {
		sc("%lld%lld", &u, &v);
		st[i] = v;
		root[v] = merge(root[v], mk(u, i));
	}
	dfs(1, 1);
	for (int i = 1; i <= N; ++i) {
		pr("%lld\n", cnt[i]);
	}
	for (int i = 1; i <= M; ++i) {
		pr("%lld\n", dep[st[i]] - die[i]);
	}
	
}

/*
5 1
50 20 10 10 30
1 1 2
2 0 5
2 0 -10
1 0 10
40 4
*/
signed main()
{
	#ifndef ONLINE_JUDGE
	//FILE_IN
	FILE_OUT
	#endif
	int T = 1;//cin >> T;
	while (T--) solve();

	return AC;
}