广州网站建设oem,wordpress随机评论头像,重庆做营销网站,大型网站开发报价方案正题
题目链接:https://www.luogu.com.cn/problem/P6847 题目大意 nnn个点的一棵树上#xff0c;每个时刻可以割掉一些边#xff0c;一些节点上有果实表示如果在did_idi时刻这个点恰好不与111联通#xff0c;那么就可以获得wiw_iwi的价值。 1≤n,k≤1051\leq n,k\leq 1…正题
题目链接:https://www.luogu.com.cn/problem/P6847 题目大意
nnn个点的一棵树上每个时刻可以割掉一些边一些节点上有果实表示如果在did_idi时刻这个点恰好不与111联通那么就可以获得wiw_iwi的价值。
1≤n,k≤1051\leq n,k\leq 10^51≤n,k≤105 解题思路
设fx,if_{x,i}fx,i表示节点xxx在时刻iii之前割掉时的最大权值那么相当与在儿子里面选一个最大的fy,j(j≤i)f_{y,j}(j\leq i)fy,j(j≤i)合并上来。
这是一个很经典的转移方式和命运那题一样直接用线段树合并维护就好了。
时间复杂度O(nlogk)O(n\log k)O(nlogk) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,m,k,rt[N],fa[N],d[N],w[N];
ll cnt,t[N5],lazy[N5],ls[N5],rs[N5];
void Downdata(int x){if(!lazy[x])return;if(ls[x])lazy[ls[x]]lazy[x],t[ls[x]]lazy[x];if(rs[x])lazy[rs[x]]lazy[x],t[rs[x]]lazy[x];lazy[x]0;return;
}
void Change(ll x,ll L,ll R,ll pos,ll val,ll z){if(!x)xcnt;if(LR){t[x]valmax(z,t[x]);return;}ll mid(LR)1;Downdata(x);if(posmid)Change(ls[x],L,mid,pos,val,z);else Change(rs[x],mid1,R,pos,val,max(z,t[ls[x]]));t[x]max(t[ls[x]],t[rs[x]]);return;
}
ll Merge(ll L,ll R,ll x,ll y,ll mx1,ll mx2){if(!x||!y){if(x)lazy[x]mx2,t[x]mx2;if(y)lazy[y]mx1,t[y]mx1;return x|y;}if(LR){t[x]max(t[x],mx1)max(t[y],mx2);return x;}ll mid(LR)1;Downdata(x);Downdata(y);rs[x]Merge(mid1,R,rs[x],rs[y],max(mx1,t[ls[x]]),max(mx2,t[ls[y]]));ls[x]Merge(L,mid,ls[x],ls[y],mx1,mx2);t[x]max(t[ls[x]],t[rs[x]]);return x;
}
signed main()
{scanf(%lld%lld%lld,n,m,k); for(ll i2;in;i)scanf(%lld,fa[i]);for(ll i1;im;i){ll x;scanf(%lld,x);scanf(%lld%lld,d[x],w[x]);}for(ll xn;x1;x--){if(d[x])Change(rt[x],1,k,d[x],w[x],0);if(fa[x])rt[fa[x]]Merge(1,k,rt[fa[x]],rt[x],0,0);}printf(%lld\n,t[rt[1]]);return 0;
}
