BZOJ3252: 攻略

3252: 攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 162 Solved: 52
[Submit][Status]

Description

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。

今天他得到了一款新游戏《XX半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

Input

第一行两个正整数n,k

第二行n个正整数，表示每个场景的价值

以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）

保证场景1为根节点

Output

输出一个整数表示答案

Sample Input

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4

Sample Output

HINT

对于100%的数据，n<=200000，1<=场景价值<=2^31-1

Source

dfs序+线段树

题解：
同学们都在复习我来机房是不是做死
你们都这么强我却在这儿刷水是不是做死
我们每次选一条最大权值的链，然后把经过该路径的点的权值都减去该点的权值，这个可以用dfs序+线段树来搞，因为每个点顶多被删1次，所以复杂度是nlogn的
代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 100000000000000ll
 24 
 25 #define maxn 500000+5
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 ll n,m,tot,a[maxn],b[maxn],fa[maxn],id[maxn],l[maxn],r[maxn],ti,head[maxn];
 61 struct seg{int l,r;ll mx[2],tag;}t[4*maxn];
 62 struct edge{int go,next;}e[maxn];
 63 bool v[maxn];
 64 inline void insert(int x,int y)
 65 {
 66     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;
 67 }
 68 inline void pushup(int k)
 69 {
 70     int l=k<<1,r=k<<1|1;
 71     t[k].mx[1]=0;
 72     if(t[l].mx[1]>t[k].mx[1])t[k].mx[1]=t[l].mx[1],t[k].mx[0]=t[l].mx[0];
 73     if(t[r].mx[1]>t[k].mx[1])t[k].mx[1]=t[r].mx[1],t[k].mx[0]=t[r].mx[0];
 74 }
 75 void build(int k,int l,int r)
 76 {
 77     t[k].l=l;t[k].r=r;int mid=(l+r)>>1;
 78     if(l==r){t[k].mx[0]=l;t[k].mx[1]=b[id[l]];return;}
 79     build(k<<1,l,mid);build(k<<1|1,mid+1,r);
 80     pushup(k);
 81 }
 82 inline void update(int k,ll z)
 83 {
 84     t[k].mx[1]-=z;
 85     t[k].tag+=z;
 86 }
 87 inline void pushdown(int k)
 88 {
 89     if(!t[k].tag)return;
 90     update(k<<1,t[k].tag);
 91     update(k<<1|1,t[k].tag);
 92     t[k].tag=0;
 93 }
 94 void add(int k,int x,int y,ll z)
 95 {
 96     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
 97     if(l==x&&r==y){update(k,z);return;}
 98     pushdown(k);
 99     if(y<=mid)add(k<<1,x,y,z);
100     else if(x>mid)add(k<<1|1,x,y,z);
101     else add(k<<1,x,mid,z),add(k<<1|1,mid+1,y,z);
102     pushup(k);
103 }
104 void dfs(int x)
105 {
106     id[l[x]=++ti]=x;
107     for(int i=head[x];i;i=e[i].next)
108     {
109         int y=e[i].go;
110         b[y]=b[x]+a[y];
111         dfs(y);
112     }
113     id[r[x]=++ti]=x;
114 }
115 
116 int main()
117 
118 {
119 
120     freopen("input.txt","r",stdin);
121 
122     freopen("output.txt","w",stdout);
123 
124     n=read();m=read();
125     for1(i,n)a[i]=read();
126     for1(i,n-1){int x=read(),y=read();fa[y]=x;insert(x,y);}
127     b[1]=a[1];
128     dfs(1);
129     build(1,1,2*n);
130     ll ans=0;
131     for1(i,m)
132     {
133         ans+=t[1].mx[1];
134         for(int j=id[t[1].mx[0]];!v[j]&&j;j=fa[j])
135         {
136             v[j]=1;
137             add(1,l[j],l[j],inf);
138             if(l[j]+1<r[j])add(1,l[j]+1,r[j]-1,a[j]);
139             add(1,r[j],r[j],inf);
140         }
141     }
142     printf("%lld
",ans);
143 
144     return 0;
145 
146 }

View Code

这是不是树上费用流的弱化版？