## 【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;
}


## 【Codeforces 736C】Ostap and Tree

### Code

#include<bits/stdc++.h>
#define LL long long
#define relax(a, b, c) (a = (a + (LL)b * c) % MOD)
using namespace std;

const int N = 300;
const int MOD = 1000000007;
const int BAS = 120;

int n, K, head[N], nxt[N], to[N];
int *f[N], arr_back[N][N];

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

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

inline void DFS(int w, int fa) {
static int arr1_back[N], *tmp = arr1_back + BAS;
f[w][-1] = f[w][K] = 1;
for (int i = head[w], t; i; i = nxt[i]) {
if ((t = to[i]) != fa) {
DFS(t, w);
for (int j = -K; j <= K; j++) {
tmp[j] = f[w][j];
f[w][j] = 0;
}
for (int j = -K; j <= K; j++) {
for (int k = -K - 1; k < K; k++) {
if (j >= 0 && k >= 0) {
relax(f[w][max(j, k)], tmp[j], f[t][k + 1]);
} else if ((j < 0 && k >= 0) || (j >= 0 && k < 0)) {
int ge = max(j, k), le = min(j, k);
if (ge + 1 >= -le) {
relax(f[w][ge], tmp[j], f[t][k + 1]);
} else {
relax(f[w][le], tmp[j], f[t][k + 1]);
}
} else {
relax(f[w][min(j, k)], tmp[j], f[t][k + 1]);
}
}
}
}
}
}

int main() {
for (int i = 1; i < n; i++) {
}
for (int i = 1; i <= n; i++) {
f[i] = arr_back[i] + BAS;
}
DFS(1, 1);
int ans = 0;
for (int i = 0; i <= K; i++) {
ans = (ans + f[1][i]) % MOD;
}
printf("%d\n", ans);
return 0;
}


## 【TopCoder SRM712】AverageVarianceSubtree

### Code

long double 最后一个点被卡精度了，只能用__float128

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

const int N = 59;
const int M = N << 1;

class AverageVarianceSubtree {
__float128 ans,tot,val[N],s1[N][N],s2[N][N],s3[N][N],cnt[N][N];
public:
double average(vector<int> p, vector<int> weight) {
memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3)); memset(cnt,0,sizeof(cnt));

n = weight.size();
for (int i=1;i<=n;i++) val[i] = weight[i - 1];
for (int i=0;i<n-1;i++) AddEdge(i + 2, p[i] + 1);
DFS(1, 1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans += (s2[i][j] - s3[i][j] / j) / j;
tot += cnt[i][j];
}
}
return ans / tot;
}
private:
inline void AddEdge(int u, int v) {
}
void DFS(int w, int f) {
cnt[w][0] = cnt[w][1] = 1;
s1[w][1] = val[w];
s2[w][1] = s3[w][1] = val[w] * val[w];
if (to[i] != f) {
DFS(to[i], w);
for (int t=n;t;t--) {
for (int a=1,b;b=t-a,a<t;a++) {
s3[w][t] += s3[w][a] * cnt[to[i]][b] + s3[to[i]][b] * cnt[w][a] + 2 * s1[w][a] * s1[to[i]][b];
s1[w][t] += s1[w][a] * cnt[to[i]][b] + s1[to[i]][b] * cnt[w][a];
s2[w][t] += s2[w][a] * cnt[to[i]][b] + s2[to[i]][b] * cnt[w][a];
cnt[w][t] += cnt[w][a] * cnt[to[i]][b];
}
}
}
}
}
};


## 【BZOJ 3566】[SHOI2014] 概率充电器

### Code

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

const int N = 500009;
const int M = N << 1;

double up[N],down[N],cost[M],q[N],vout;

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 f) {
static int E = 1;
cost[E+1] = cost[E+2] = f / 100.0;
}

void DFS1(int w, int f) {
down[w] = 1 - q[w];
if (to[i] != f) {
DFS1(to[i], w);
down[w] *= down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]);
}
}
}

void DFS2(int w, int f, double p) {
vout += 1 - (up[w] = down[w] * p);
if (to[i] != f) {
double tmp = p * down[w] / (down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]));
DFS2(to[i], w, tmp + (1 - tmp) * (1 - cost[i]));
}
}
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
for (int i=1;i<=n;i++) q[i] = read() / 100.0;
DFS1(1, 1);
DFS2(1, 1, 1);
printf("%.6lf\n",vout);
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 4455】[ZJOI2016] 小星星

### 解题报告

$f(i,j,S)$ 表示树上第$i$个点，对应图中第$j$个点，子树中的对应状态状压后为$S$的方案数

1. 这样会T
2. 我不会更优的算法了

## 【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(){