## 【Codeforces 815C】Karen and Supermarket

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const LL INF = 1e14;

int n, head[N], nxt[N], to[N], sz[N];
LL b, f[N][N], g[N][N], c[N], d[N], t1[N], t2[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void relax(LL &a, LL b) {
a = a > b? b: a;
}

inline void DFS(int w) {
f[w][0] = g[w][0] = 0;
for (int i = head[w]; i; i = nxt[i]) {
DFS(to[i]);
memcpy(t1, f[w], sizeof(t1));
memcpy(t2, g[w], sizeof(t2));
for (int j = 0; j <= sz[w]; j++) {
for (int k = 0; k <= sz[to[i]]; k++) {
relax(f[w][j + k], t1[j] + f[to[i]][k]);
relax(g[w][j + k], t2[j] + g[to[i]][k]);
}
}
sz[w] += sz[to[i]];
}
sz[w]++;
for (int i = sz[w] - 1; ~i; i--) {
g[w][i + 1] = g[w][i] + c[w] - d[w];
relax(f[w][i + 1], f[w][i] + c[w]);
relax(g[w][i + 1], f[w][i + 1]);
}
g[w][0] = 0;
}

int main() {
for (int i = 2; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = g[i][j] = INF;
}
}
DFS(1);
for (int i = n; ~i; i--) {
if (g[1][i] <= b) {
printf("%d\n", i);
exit(0);
}
}
return 0;
}


## 【日常小测】tree

### 解题报告

$f_{i,j}$表示在$i$的子树里，选$j$个点，直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里，选$j$个点，已经考虑过直径且直径不包含$i$的最小花费

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;

LL vout=INF,f[N][N],g[N][N],h[N][N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
}

void update(int w, int fa) {
fill(f[w], f[w]+1+N, INF);
fill(g[w], g[w]+1+N, INF);
fill(h[w], h[w]+1+N, INF);
f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
if ((t=to[i]) != fa) {
update(to[i], w);
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++)
h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
}
sz[w] += sz[t];
}
}
vout = min(vout, f[w][k]);
vout = min(vout, g[w][k]);
}

int main() {
for (int i=2,u,v;i<=n;i++) {
}
update(1, 1);
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 4753】[JSOI2016] 最佳团体

### 解题报告

1. 选择第i+1个点：$f(i+1,j+1) = f(i+1,j+1) + f(i,j) + w_{i+1}$
2. 不选择第i+1个点：$f(r(i+1)+1,j) = f(r(i+1)+1,j) + f(i,j)$

## 【BZOJ 1040】[ZJOI2008] 骑士

### 题解

I well vegetable are!

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = N << 1;

int n,val[N],aim[N],tag[N],lb,rb;
LL vout,f[N][2];

inline void Add_Edge(const int u, const int v) {
static int T = 1;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void DFS(int w, int f) {
tag[w] = 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f && to[i]) {
if (tag[to[i]]) {
lb = w; rb = to[i];
to[i] = to[i^1] = 0;
} else {
DFS(to[i], w);
}
}
}

void solve(int w, int fa) {
f[w][0] = 0;
f[w][1] = val[w];
for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != fa) {
solve(to[i], w);
f[w][1] += f[to[i]][0];
f[w][0] += max(f[to[i]][1],f[to[i]][0]);
}
if (tag[w] == 2) {
f[w][0] = 0;
} else if (tag[w] == 3) {
f[w][1] = 0;
}
}

int main(){
for (int i=1,t;i<=n;i++) {
aim[i] = t;
}
}
for (int i=1;i<=n;i++) {
if (!tag[i]) {
LL tmp;
lb = rb = 0;
DFS(i,i);

tag[lb] = 2; tag = 3;
solve(i,i);
tmp = max(f[i][0], f[i][1]);

tag[lb] = 3; tag = 2;
solve(i,i);
tmp = max(tmp, max(f[i][0], f[i][1]));

tag[lb] = 3; tag = 3;
solve(i,i);
tmp = max(tmp, max(f[i][0], f[i][1]));
vout += tmp;
}
}
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 2286】[Sdoi2011] 消耗战

DP很好想，只需要会建虚树就可以辣！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int SGZ = 18;
const int M = 500000+9;
const int N = 250000+9;
const int INF = 0x7fffffff;

int n,m,p[N],num[N],stk[N],top,tot,T;
bool vis[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
}

inline void Add_Edge(int u, int v, int w) {
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
static int dfs_cnt = 0; num[w] = ++dfs_cnt;
fa[w][0] = f; dep[w] = dep[f] + 1;
if (to[i] != f) {
DFS(to[i], w);
MN[to[i]][0] = cost[i];
}
}
}

inline bool CMP(const int &x, const int &y) {
return num[x] < num[y];
}

inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return x;
for (int i=17;~i;i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}

inline int Get_Cost(int w, int pur) {
int ret = INF; pur = dep[pur];
for (int i=17;~i;i--) {
if (dep[fa[w][i]] >= pur) {
ret = min(ret, MN[w][i]);
w = fa[w][i];
}
}
return ret;
}

inline void build() {
stk[top = 1] = 1;
for (int i=1,w,lca;i<=m;i++) {
w = p[i]; lca = LCA(stk[top], w);
while (dep[stk[top]] > dep[lca]) {
if (dep[stk[top-1]] <= dep[lca])
else
--top;
}
if (stk[top] != lca) stk[++top] = lca, p[++tot] = lca;
stk[++top] = w;
}
for (int i=1;i<top;i++)
}

inline LL DP(int w, int f) {
LL tmp = 0;
tmp += DP(to[i], w);
if (vis[w]) return Get_Cost(w, f);
else if (w != 1) return min((LL)Get_Cost(w, f), tmp);
else return tmp;
}

int main() {
for (int i=1,u,v;i<n;i++) {
}

DFS(1, 1); MN[1][0] = INF;
for (int j=1;j<=17;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
MN[i][j] = min(MN[i][j-1], MN[fa[i][j-1]][j-1]);
}
}

m = tot = read(); T = 0;
for (int i=1;i<=m;i++) vis[p[i] = read()] = 1;
sort(p+1, p+1+m, CMP);
build();
for (int i=1;i<=tot;i++) vis[p[i]] = 0, head[p[i]] = 0;
}
return 0;
}


## 【BZOJ 3829】[POI2014] FarmCraft

#include<bits/stdc++.h>
using namespace std;

const int N = 500000+9;
const int M = 1000000+9;

int n,tmp[N],beg[N],end[N],tot,C1;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

inline bool CMP(const int &a, const int &b) {
return max(f[a],g[a]+2+f[b]) < (f[b],g[b]+2+f[a]);
}

void DP(int w, int fa) {
int cnt = 0;
if (to[i] != fa) cnt++;
}
beg[w] = tot + 1;
end[w] = (tot += cnt); cnt = -1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != fa) {
DP(to[i],w);
g[w] += g[to[i]] + 2;
tmp[beg[w]+(++cnt)] = to[i];
}
if (beg[w] <= end[w]) {
sort(tmp+beg[w],tmp+end[w]+1,CMP);
}
for (int i=beg[w],sum=0;i<=end[w];i++) {
f[w] = max(f[w], f[tmp[i]] + sum + 1);
sum += g[tmp[i]] + 2;
}
}

int main(){