记得复习！45iu很认同此氢氧化钠吗34
区间DP
P1220 关路灯
主要是状态设计和【费用提前计算】这两个要点有一点思维难度，但是懂得了之后就很容易了
f[l][r][0/1] 代表区间 [L,R] 且 0/1 对应此时站在 L/R 处位置
之后每次以 f[l+1][r] 和 f[l][r-1] 进行转移，让费用进行提前计算
P4870 BalticOI 2009 Day1 甲虫
可以理解为 关路灯 的加强版。虽然我当时做了关路灯但是还是不知道如何做出这道题
费用肯定是要提前计算的，考虑每走一次减去蒸发的水量，而每到一个点加上m。
然后发现我们不知道甲虫会走到哪里，很难转移。
所以额外增加循环：
由于无法统计蒸发的水量（不知道最后走到哪里就可以不动了），所以
考虑增加一层循环N枚举最终吃掉的水的区间长度。合法性是因为走过水必然会吃，所以吃掉的水必为连续区间。
f(l,r,0/1) 区间l~r，在l/r
状态提前计算：
由于无法记录时间，所以考虑提前减去蒸发的水量。每到一个新的点就
加上m即可。
树形DP
一般来说换根dp第一遍求出来1为根的正确信息（正常树形dp）,第二次每个点从父亲转移而不是从儿子转移
P2607 [ZJOI2008] 骑士
第一次做基环树dp。可以发现与【没有上司的舞会】非常像，只是变成了一个基环树（树再加上一条边）
另外，这题不一定是连通图，一个连通块中有一个环（有向边）。
所以这样处理：容易发现基环树只会有一个环（毕竟是树加一条边），我们找到那条环，之后从中找一条边断开，之后从断开的两个点分别进行树形dp（原因见下），这个dp不一定非要限制在此环中。
一些细节：
- 建边的时候从自己憎恨的人指向自己，也即自己憎恨的人是父节点，同时记录fa[x]，方便找环（与边不一样，是倒着找环）由于自己只会憎恨一个人，也就是只有一个父亲，所以树形dp是可行的。（倒着找环的原因也在此，因为只有一个父亲，所以要从自己走向父亲，保证路径唯一）
- 断的边两端点不能同时取得，两次dp的原因也在此，每次的时候控制不取自己（但是从另一个节点进行dp就可以取了），另一个点随意，所以两个点有【不取，不取】和【不取，取】两种可能，另一次dp也同样。所以分别取两次节点都包含在内了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
int n,w[N],fa[N],rt;ll f[N][2];
bool st[N];
int h[N],e[N],ne[N],idx;ll ans;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
st[u]=1;f[u][0]=0;f[u][1]=w[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(rt!=j){
dfs(j);
f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];
}
else f[j][1]=-2e9;
//由于是深度优先，所以此时f[j][1]还未更新
}
}
void fcir(int u){//即FindCircle
st[u]=1;
while(!st[fa[u]]){
u=fa[u];
st[u]=1;
}
rt=u;
dfs(u);
ll t=max(f[u][0],f[u][1]);
u=fa[u];
rt=u;
dfs(u);
ans+=max(t,max(f[u][0],f[u][1]));
}
signed main(){
memset(h,-1,sizeof(h));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);int x;
scanf("%d",&x);add(x,i);
fa[i]=x;
}//注意每个点是仇人连向自己，而自己只有一个仇人
//因此一定是一颗外向树，即不会有两条边指向同一个点（有向边）
for(int i=1;i<=n;i++)
if(!st[i]) fcir(i);
printf("%lld",ans);
return 0;
}
P3647 [APIO2014] 连珠线
byd最恶心的一集，这题太麻烦了。
首先是错误解法，直接根据题意dp，但是如下数据就无法处理了
7
1 2 1
2 3 1
2 4 1
1 5 1
5 6 1
5 7 1
ans=4(not 6)
可以发现是 son-x-son这种情况会出现问题，而son-x-fa不会有问题
观察到指定根不同的时候，若只进行son-x-fa转移，一定能得到合法的最优解，所以进行换根dp
剩下的看其他题解吧，这只是个做题记录给自己复习用的，一点点解释太麻烦了
P1453 城市环路
与前面ZJOI骑士基本一致，区别不过是①没有规定每个人只有一个敌人之类的说法，因此得连双向边 ②保证联通
首先，关于双向边找环，dfs可能爆栈，而又无法进行循环，所以考虑并查集。
之后可以发现并查集的神奇用处：若两个点已经在一个环中，那么记录它们并且不用连边，这样就保证了没有边在环上，而由于保证只有一环，而当发现两个点发现在一个环上的时候，这条边没有连上，所以没有形成环，故而只会删掉一条边，然后就简单多了。
这道题的思路相比前面的骑士一题又有了进步
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10,inf=0x3f3f3f3f;
int n,rt,p1,p2;db k,w[N],ans;
int h[N],e[N],ne[N],idx;db f[N][2];
int p[N];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
bool st[N],flag;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//错误的找环：
//void dfs1(int x,int last){
// if(flag) return;
// if(st[x]){
// p1=x,p2=last;
// flag=1;
// return;
// }
// st[x]=1;
// for(int i=h[x];~i;i=ne[i]){
// int j=e[i];
// if(j==last||flag) continue;
// if(st[j]){
// p1=j;p2=x;
// flag=1;
// return;
// }
// dfs1(j,x);
// }
//}
void dfs(int x,int last){
f[x][0]=0,f[x][1]=(x==rt?-2e9:w[x]);
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(j==last) continue;
dfs(j,x);
f[x][1]+=f[j][0];
f[x][0]+=max(f[j][1],f[j][0]);
/*
错误的转移
f[x][1]=max(f[x][1],f[j][0]+w[x]*k);
f[x][0]=max(f[j][1],f[j][0]);
*/
}
}
signed main(){
memset(h,-1,sizeof(h));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&w[i]),p[i]=i;
for(int i=1,a,b;i<=n;i++){
scanf("%d%d",&a,&b);a++;b++;
int pa=find(a),pb=find(b);
if(pa==pb&&!p1){
p1=a,p2=b;continue;
}
else p[pa]=pb;
add(a,b);add(b,a);//并查集
}
scanf("%lf",&k);
dfs(p1,-1);ans=f[p1][0];
dfs(p2,-1);ans=max(ans,f[p2][0]);
printf("%.1lf",ans*k);
return 0;
}
P6419 [COCI2014-2015#1] Kamp
明显换根dp，一开始设计f0表示以i为根的子树中有一条路径只需要走一遍其余走两遍的最小值，f1都走两遍的最小值，之后进行换根dp（同时用gi数组记录i子树中有人的点的数量）
之后发现换根转移特别答辩（其实我也不知道是不是细节问题或者我想复杂了）但是我两个小时都没调出来只好看题解。
这主要是给我自己看的，如果有别人想看的话看这位的题解，下面不过是截图罢了
期望/概率dp
过河 Crossing Rivers
概率最基本的题目，根本用不上dp。
对于每条河，最好和最坏的情况分别是到河边的时候船刚好到和刚好离开
分别所需时间为 l/v和3l/v，因为各种概率均匀分布（期望的线性性）所以平均概率为2*l/v
每条河分别求，加上陆地上时间即可
FAVDICE - Favorite Dice
简介：n面骰子，期望投多少次每面都会投到一次
考虑期望dp：（设 fi 表示已经投出了 n 个不同的面仍需的期望次数）
fi=i/n×fi+(n−i)/n×fi+1+1
将其转化为递推式发现 fi=fi+1+n/(n−i) ，也即 ANS=n/i(1<=times<=n)
[AGC030D] Inversion Sum
关键的难点在于转化，将一个不可做的东西转化为概率dp，转移和状态设计均十分精妙。
考虑拆分贡献，单独考虑每个逆序对
转化为概率dp，f[i][j]表示位置i的数<位置j的数的概率
而每个(i,j)的次数和就是 f[i][j]*2^q（因为2^q是一共的操作子序列个数，概率乘上这个就是这对逆序对出现的次数）
转移：
f[x][i]=f[y][i]=(f[x][i]+f[y][i])/2
f[i][x]=f[i][y]=(f[i][x]+f[i][y])/2
Init: 初始状态下 a[i]<a[j]，f[i][j]=1
calc: 统计所有j<i的f[i][j]之和，再乘上2^q(因为是逆序对，所以j<i)
因为x,y有1/2的概率交换，也就是 f[x][i]×0.5+f[y][i]×0.5的经典概率dp形式
不过正常人怎么可能想到把这个转化为抽象，似乎还不确定的概率问题啊？！ 真的离谱
Little Elephant and Broken Sorting
可以发现与上一题一样，甚至还是弱化版，只需要求出概率即可。
和上一题完全一样的做，期望的和等于和的期望，将每个逆序对的期望相加即可。
