额...左偏树（可并堆）。
两件事情，1：需要用到lazy标记（左偏树是二叉数据结构，可以PushDown）2.用到lazy标记时，注意先乘后加（在打标记的时候修改加法标记）
剩下的，就是dfs模拟（有一些奇怪的OJ会发生爆栈的鬼畜事情）
维护小根堆，以能到达这个节点的骑士的战斗力为排序基准
之后每次删除不能满足的节点，剩下的就是类板子了，可以放心食用
递归版
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define N 300005 10 #define ll long long 11 struct node 12 { 13 int ls,rs,dis;ll x,add,mul; 14 }mp[N<<1]; 15 struct no 16 { 17 int to,next; 18 }e[N]; 19 ll h[N],v[N]; 20 int head[N],cnt,fa[N],dep[N],a[N],siz[N],ans[N],s[N],n,m; 21 void add(int x,int y) 22 { 23 e[cnt].to=y; 24 e[cnt].next=head[x]; 25 head[x]=cnt++; 26 return ; 27 } 28 void PushDown(int x) 29 { 30 if(mp[x].mul!=1) 31 { 32 mp[mp[x].ls].x*=mp[x].mul; 33 mp[mp[x].rs].x*=mp[x].mul; 34 mp[mp[x].ls].mul*=mp[x].mul; 35 mp[mp[x].rs].mul*=mp[x].mul; 36 mp[mp[x].ls].add*=mp[x].mul; 37 mp[mp[x].rs].add*=mp[x].mul; 38 mp[x].mul=1; 39 } 40 if(mp[x].add) 41 { 42 if(mp[x].ls) 43 mp[mp[x].ls].x+=mp[x].add,mp[mp[x].ls].add+=mp[x].add; 44 if(mp[x].rs) 45 mp[mp[x].rs].x+=mp[x].add,mp[mp[x].rs].add+=mp[x].add; 46 mp[x].add=0; 47 } 48 } 49 int merge(int x,int y) 50 { 51 if(!x)return y; 52 if(!y)return x; 53 if(mp[x].x>mp[y].x)swap(x,y); 54 PushDown(x); 55 mp[x].rs=merge(mp[x].rs,y); 56 if(mp[mp[x].rs].dis>mp[mp[x].ls].dis)swap(mp[x].ls,mp[x].rs); 57 mp[x].dis=mp[mp[x].rs].dis+1; 58 return x; 59 } 60 void dfs(int x,int from) 61 { 62 for(int i=head[x];i!=-1;i=e[i].next) 63 { 64 int to1=e[i].to; 65 dep[to1]=dep[x]+1; 66 dfs(to1,x); 67 int fx=fa[x],fy=fa[to1]; 68 fa[x]=merge(fx,fy); 69 } 70 if(!fa[x])return ; 71 int fx=fa[x]; 72 while(mp[fx].x
非递归版
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define N 300005 10 #define ll long long 11 struct node 12 { 13 int ls,rs,dis;ll x,add,mul; 14 }mp[N<<1]; 15 struct no 16 { 17 int to,next; 18 }e[N]; 19 ll h[N],v[N]; 20 int head[N],cnt,fa[N],dep[N],a[N],siz[N],ans[N],s[N],n,m; 21 void add(int x,int y) 22 { 23 e[cnt].to=y; 24 e[cnt].next=head[x]; 25 head[x]=cnt++; 26 return ; 27 } 28 void PushDown(int x) 29 { 30 if(mp[x].mul!=1) 31 { 32 mp[mp[x].ls].x*=mp[x].mul; 33 mp[mp[x].rs].x*=mp[x].mul; 34 mp[mp[x].ls].mul*=mp[x].mul; 35 mp[mp[x].rs].mul*=mp[x].mul; 36 mp[mp[x].ls].add*=mp[x].mul; 37 mp[mp[x].rs].add*=mp[x].mul; 38 mp[x].mul=1; 39 } 40 if(mp[x].add) 41 { 42 if(mp[x].ls) 43 mp[mp[x].ls].x+=mp[x].add,mp[mp[x].ls].add+=mp[x].add; 44 if(mp[x].rs) 45 mp[mp[x].rs].x+=mp[x].add,mp[mp[x].rs].add+=mp[x].add; 46 mp[x].add=0; 47 } 48 } 49 int merge(int x,int y) 50 { 51 if(!x)return y; 52 if(!y)return x; 53 if(mp[x].x>mp[y].x)swap(x,y); 54 PushDown(x); 55 mp[x].rs=merge(mp[x].rs,y); 56 if(mp[mp[x].rs].dis>mp[mp[x].ls].dis)swap(mp[x].ls,mp[x].rs); 57 mp[x].dis=mp[mp[x].rs].dis+1; 58 return x; 59 } 60 int f[N]; 61 void dfs(int x) 62 { 63 f[1]=0; 64 while(x) 65 { 66 int son=0; 67 for(int i=head[x];i!=-1;i=e[i].next) 68 { 69 int to1=e[i].to; 70 if(to1!=f[x]) 71 { 72 f[to1]=x; 73 dep[to1]=dep[x]+1; 74 head[x]=e[i].next; 75 x=to1; 76 son=1; 77 break; 78 } 79 } 80 if(!son) 81 { 82 if(!fa[x]) 83 { 84 x=f[x]; 85 continue; 86 } 87 int fx=fa[x]; 88 while(mp[fx].x
bfs版没有写...