#include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<vector> #include<bitset> using namespace std; typedef long long ll; const int n = 100000 + 100; vector<int> son[n]; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll m,a[n],w[n],siz[n]; int ch[n][2],fa[n],n,dist[n]; ll ans,num[n]; int merge(int x,int y) { if(x == 0 || y == 0) return x == 0 ? y : x; if(a[x] > a[y] || (x > y && a[x] == a[y])) swap(x,y); ch[y][1] = merge(x,ch[y][1]); fa[x] = y; if(dist[ch[y][1]] > dist[ch[y][0]]) swap(ch[y][1],ch[y][0]); dist[y] = dist[ch[y][1]] + 1; return y; } ll pop(int x) { int k = merge(ch[x][0],ch[x][1]); ch[x][1] = ch[x][0] = 0; siz[k] = siz[x] - a[x]; num[k] = num[x] - 1; return k; } int dfs(int u) { int nn = son[u].size(); int now = u; siz[now] = a[now]; num[now] = 1; for(int i = 0;i < nn;++i) { int v = son[u][i]; int k = dfs(v); int ls = merge(k,now); siz[ls] = siz[k] + siz[now]; num[ls] = num[k] + num[now]; now = ls; } while(siz[now] > m) now = pop(now); ans = max(ans,w[u] * num[now]); return now; } int main() { n = read(), m = read(); dist[0] = -1; int rt = 0; for(int i = 1;i <= n;++i) { int fat = read(); a[i] = read(),w[i] = read(); son[fat].push_back(i); if(fat == 0) rt = i; } dfs(rt); cout<<ans; return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论