考虑在树上进行左偏树的合并
有一要点是进行乘法的时候记得更新加法的标记
#include<iostream>
#define int long long
using namespace std;
struct LeftNode { int v, left, right, dist, atag, mtag; }lt[300005];
struct Edge { int end, next; }e[300005];
struct Node { int d, a, v, rt, dep; }t[300005];
int head[300005], cnt;
void addedge(int u, int v) { e[++cnt] = { v,head[u] }, head[u] = cnt; }
void down(int p)//真神push_down的繁琐稳定发挥
{
lt[lt[p].left].atag *= lt[p].mtag;//先乘后加,更新加法标记
lt[lt[p].left].v *= lt[p].mtag;
lt[lt[p].left].mtag *= lt[p].mtag;
lt[lt[p].left].atag += lt[p].atag;
lt[lt[p].left].v += lt[p].atag;
lt[lt[p].right].atag *= lt[p].mtag;
lt[lt[p].right].v *= lt[p].mtag;
lt[lt[p].right].mtag *= lt[p].mtag;
lt[lt[p].right].atag += lt[p].atag;
lt[lt[p].right].v += lt[p].atag;
lt[p].atag = 0, lt[p].mtag = 1;
}
int merge(int p, int q)//左偏树合并的板子
{
if (!p || !q)return p | q;
if (lt[p].v > lt[q].v)swap(p, q);
down(p);//只多了push_down,因为我们要访问p的孩子,所以对它push_down
lt[p].right = merge(lt[p].right, q);
if (lt[lt[p].right].dist > lt[lt[p].left].dist)swap(lt[p].left, lt[p].right);
lt[p].dist = lt[lt[p].right].dist + 1;
return p;
}
int city_ans[300005], knight_ans[300005], st[300005];//存答案的
void dfs(int s)
{
for (int i = head[s];i;i = e[i].next)
{
t[e[i].end].dep = t[s].dep + 1;
//深度,对于没有阵亡的骑士,其答案为其初始城池的深度(1号城深度为1)
dfs(e[i].end);
t[s].rt = merge(t[s].rt, t[e[i].end].rt);//合并自己与儿子的左偏树
}
while (t[s].rt && lt[t[s].rt].v < t[s].d)
{
knight_ans[t[s].rt] = t[st[t[s].rt]].dep - t[s].dep;
++city_ans[s];
down(t[s].rt);//记得push_down
t[s].rt = merge(lt[t[s].rt].left, lt[t[s].rt].right);
}
if (!t[s].rt)return;
if (t[s].a)
{
lt[t[s].rt].atag *= t[s].v;
lt[t[s].rt].mtag *= t[s].v;
lt[t[s].rt].v *= t[s].v;
}
else
{
lt[t[s].rt].atag += t[s].v;
lt[t[s].rt].v += t[s].v;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;++i)cin >> t[i].d;
for (int i = 2, f;i <= n;++i)
{
cin >> f >> t[i].a >> t[i].v;
addedge(f, i);
}
for (int i = 1;i <= m;++i)
{
cin >> lt[i].v >> st[i];
lt[i].mtag = 1;
knight_ans[i] = -1;
t[st[i]].rt = merge(t[st[i]].rt, i);
}
t[1].dep = 1;
dfs(1);
for (int i = 1;i <= n;++i)cout << city_ans[i] << '\n';
for (int i = 1;i <= m;++i)
{
if (~knight_ans[i])cout << knight_ans[i] << '\n';
else cout << t[st[i]].dep << '\n';
}
}