P1552 [APIO2012] 派遣 题解

一、题目描述：

　　给你一个 $n$ 个点的有根树，每个点有两个参数 $w$ 和 $v$ 。再给出一个数 $m$ 。

　　对于每一个点 $u$ ，设它的子树内最多可以选择 $k_u$ 个点 $a_1,a_2,...,a_{k_u}$，使得 $\sum _{i=1}^k w_{a_i} \le m$ 。

　　那么点 $u$ 的价值为 $v_u \times k_u$，求 $max(\sum_{i=1}^{n} v_i \times k_i)$ 。

　　数据范围：$1 \le n \le 1 \times 10^5,1 \le w_i \le m \le 1 \times 10^9,1 \le v_i \le 1 \times 10^9 $ 。

 二、解题思路：

　　思路很明显，直接从儿子向父亲合并信息即可。

　　然后不停的 $pop$ ，直到 $sum \le m$ 。

　　用的是左偏树，时间复杂度 $O(nlog_2^n)$，注意开 $long long$ 。

 三、完整代码：

 1 #include<iostream>
 2 #define N 100010
 3 #define d(p) t[p].d
 4 #define ls(p) t[p].ls
 5 #define rs(p) t[p].rs
 6 #define val(p) t[p].val
 7 using namespace std;
 8 int n,m,fa;
 9 long long ans,sum[N];
10 int a[N],rt[N],size[N];
11 struct EDGE{
12     int v,nxt;
13 }edge[N];
14 int head[N],cnt;
15 void add(int u,int v)
16 {
17     edge[++cnt].v=v;
18     edge[cnt].nxt=head[u];
19     head[u]=cnt;
20 }
21 struct Node{
22     int d,ls,rs,val;
23 }t[N];
24 int merge(int p,int q)
25 {
26     if(!p||!q)    return p|q;
27     if(val(p)<val(q)) swap(p,q);
28     rs(p)=merge(rs(p),q);
29     if(d(ls(p))<d(rs(p))) swap(ls(p),rs(p));
30     d(p)=d(rs(p))+1; return p;
31 }
32 int pop(int u)
33 {
34     size[u]--;sum[u]-=val(rt[u]);
35     return merge(ls(rt[u]),rs(rt[u]));
36 }
37 void dfs(int u)
38 {
39     for(int i=head[u];i!=-1;i=edge[i].nxt)
40     {
41         int to=edge[i].v;dfs(to);
42         rt[u]=merge(rt[u],rt[to]);
43         sum[u]+=sum[to],size[u]+=size[to];
44         while(sum[u]>m) rt[u]=pop(u);
45     }
46     while(sum[u]>m) rt[u]=pop(u);
47     ans=max(ans,1ll*size[u]*a[u]);
48 }
49 int main()
50 {
51     ios::sync_with_stdio(false);
52     cin.tie(0);cout.tie(0);
53     cin>>n>>m;t[0].d=-1;
54     for(int i=1;i<=n;i++)
55         head[i]=-1;
56     for(int i=1;i<=n;i++)
57     {
58         cin>>fa>>val(i)>>a[i];rt[i]=i;
59         add(fa,i),sum[i]=val(i),size[i]=1;
60     }
61     dfs(1);cout<<ans<<'\n';
62     return 0;
63 }

四、写题心得：

　　算是左偏树模板，没什么思维难度，收获经验如下：

　　$1、merge\ 函数是重点，但并不难写。=> Exp++!$

　　$2、pop\ 的时候记得是访问\ rt_u\ ，在这里卡了好久。=> Exp++! $