题解：
第一题：类比只有三根，四根的柱子的汉诺塔，柱子越多越好，柱子盘子固定，步数一定，如果我有K个盘子，J个柱子，把P个盘子移到1个柱子的步数为F【P】【J】， 那么剩余K-P个盘子移到1个柱子就是F【K-P】【J-1】， 放P的柱子不能再放了，然后我们又有J个可以自由移动的柱子，
所以f[ i ][ j ] = min(f[ k ][ j ] * 2 + f[ i - k ][ j -1 ]), 枚举k即可；
#includeusing namespace std; long long dp[70][70];int main(){freopen("hanoi.in","r",stdin);freopen("hanoi.out","w",stdout);int n, m;scanf("%d%d", &n, &m);memset(dp, 0x3f, sizeof(dp));dp[1][3] = 1;for(int i = 2; i <= n; i++) dp[i][3] = ((dp[i - 1][3] + 1) << 1) - 1;for(int i = 1; i <= 65; i++) dp[0][i] = 0, dp[1][i] = 1, dp[2][i] = 3;for(int i = 4; i <= m; i++)for(int j = 3; j <= n; j++){for(int k = 1; k <= j; k++)dp[j][i] = min(2 * dp[j - k][i] + dp[k][i - 1], dp[j][i]);}printf("%lld ", dp[n][m]); }
第二题：
我只想说cyj太聪明了
#includeusing namespace std; const int M = 200005; char s[M]; int b[M]; struct node{int val, id;bool operator < (const node &rhs) const{return val < rhs.val;} }a[M];int q[M], h, t; int main(){freopen("rank.in","r",stdin);freopen("rank.out","w",stdout);int n, fg = 0;scanf("%d", &n);char now = 'a';for(int i = 1; i <= n; i++){scanf("%d", &a[i].val), a[i].id = i; b[i] = a[i].val;}sort(a + 1, a + 1 + n);int lst = 0; a[n+1].id = -1;for(int i = 1; i <= n; i++){node p; p.val = i;int pos = lower_bound(a + 1, a + 1 + n, p) - a;if(b[a[pos].id + 1] > lst) s[a[pos].id] = now;else s[a[pos].id] = ++now;lst = b[a[pos].id + 1];if(now > 'z'){fg = -1;break;}}if(fg)puts("-1");else for(int i = 1; i <= n; i++)printf("%c", s[i]); }
第三题：期望DP，以前讲过， 终于还是写了这道题
F化简：f(u) = sum ( f(v) ) + deg(u) , v is u's child
G化简：g(u) = g(fa(u)) + f(fa(u)) - f(u);
注意求完f,然后用f更新g, 修改f[ 1 ] = 0, 因为1不会再往上走，但更新g之前不能改F1，是有实际有意的；
#includeusing namespace std; #define ex(i, u) for(int i = h[u]; i; i = G[i].nxt) const int mod = 1e9 + 7, M = 1e5 + 5; int P = 20, f[M], g[M], F[M], GV[M], dep[M], deg[M], anc[M][25], h[M], tot; struct edge{ int nxt, v;}G[M<<1]; void add(int u, int v){G[++tot].v = v, G[tot].nxt = h[u], h[u] = tot;} inline int moc(int a){ return a >= mod ? a - mod : a;} void dfs1(int u, int fa){anc[u][0] = fa;for(int p = 1; p <= P; p++)anc[u][p] = anc[anc[u][p - 1]][p - 1];ex(i, u){int v = G[i].v;if(v == fa)continue;dfs1(v, u);f[u] = moc(f[u] + f[v]);}f[u] = moc(f[u] + deg[u]); }void dfs2(int u, int fa){dep[u] = dep[fa] + 1; F[u] = moc(F[fa] + f[u]);GV[u] = moc(GV[fa] + g[u]);ex(i, u){int v = G[i].v;if(v == fa)continue;g[v] = (g[u] + f[u] - f[v] + mod) % mod;dfs2(v, u);} }int get(int u, int v){if(dep[u] < dep[v])swap(u, v);int t = dep[u] - dep[v];for(int p = 0; t; t >>= 1, p++)if(t & 1) u = anc[u][p];if(u == v) return u;for(int p = P; p >= 0; p--)if(anc[u][p] != anc[v][p])u = anc[u][p], v = anc[v][p];return anc[u][0]; }int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);int n, q, u, v;scanf("%d%d", &n, &q);for(int i = 1; i < n; i++){scanf("%d%d", &u, &v);add(u, v); add(v, u);deg[u]++; deg[v]++;}dfs1(1, 0);F[0] = -f[1];dfs2(1, 0);//for(int i = 1; i <= n; i++)printf("%d %d %d %d %d ", i, f[i], g[i], F[i], GV[i]);f[1] = 0;while(q--){scanf("%d%d", &u, &v);int lca = get(u, v), flca = anc[lca][0];int ans = ( (F[u] - F[lca] + GV[v] - GV[lca]) % mod + mod ) % mod;printf("%d ", ans);} }