T1 染色
直接操作分块，可以做到 \(O(n\sqrt{n})\) 。（显然树剖求 lca 约为 \(O(1)\) ）
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int max1 = 1e5, B = 300;
int n, m;
vector <int> edge[max1 + 5];
int father[max1 + 5], val[max1 + 5];
long long sum[max1 + 5];
int siz[max1 + 5], deep[max1 + 5], son[max1 + 5];
int top[max1 + 5], dfn[max1 + 5], rk[max1 + 5], dfs_clock;
int tmp[max1 + 5], len;
bool black[max1 + 5];
int cnt[max1 + 5];
long long f[max1 + 5], g[max1 + 5];
void Find_Heavy_Edge ( int now, int depth )
{
sum[now] = sum[father[now]] + val[now];
siz[now] = 1, deep[now] = depth, son[now] = 0;
int max_siz = 0;
for ( auto v : edge[now] )
{
Find_Heavy_Edge(v, depth + 1);
if ( siz[v] > max_siz )
max_siz = siz[v], son[now] = v;
siz[now] += siz[v];
}
return;
}
void Connect_Heavy_Edge ( int now, int ancestor )
{
top[now] = ancestor;
dfn[now] = ++dfs_clock;
rk[dfs_clock] = now;
if ( son[now] )
Connect_Heavy_Edge(son[now], ancestor);
for ( auto v : edge[now] )
{
if ( v == son[now] )
continue;
Connect_Heavy_Edge(v, v);
}
return;
}
int Get_Lca ( int u, int v )
{
while ( top[u] != top[v] )
{
if ( deep[top[u]] < deep[top[v]] )
swap(u, v);
u = father[top[u]];
}
if ( deep[u] > deep[v] )
swap(u, v);
return u;
}
long long Get_Dis ( int u, int v )
{
return sum[u] + sum[v] - (sum[Get_Lca(u, v)] << 1);
}
void Solve ()
{
memset(cnt + 1, 0, sizeof(int) * n);
memset(f + 1, 0, sizeof(long long) * n);
len = 0;
for ( int i = n; i >= 2; i -- )
{
int now = rk[i];
cnt[now] += (int) black[now];
f[father[now]] += f[now] + 1LL * cnt[now] * val[now];
cnt[father[now]] += cnt[now];
}
cnt[1] += (int) black[1];
g[1] = f[1];
for ( int i = 2; i <= n; i ++ )
{
int now = rk[i];
g[now] = g[father[now]] + 1LL * (cnt[1] - cnt[now] - cnt[now]) * val[now];
}
return;
}
int main ()
{
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 2; i <= n; i ++ )
{
scanf("%d", &father[i]); ++father[i];
edge[father[i]].push_back(i);
}
for ( int i = 2; i <= n; i ++ )
scanf("%d", &val[i]);
Find_Heavy_Edge(1, 0);
Connect_Heavy_Edge(1, 1);
int opt, x;
for ( int i = 1; i <= m; i ++ )
{
scanf("%d%d", &opt, &x); ++x;
if ( opt == 1 )
{
if ( !black[x] )
{
tmp[++len] = x;
black[x] = true;
}
}
else
{
long long ans = g[x];
for ( int k = 1; k <= len; k ++ )
ans += Get_Dis(x, tmp[k]);
printf("%lld\n", ans);
}
if ( !(i % B) )
Solve();
}
return 0;
}
T2 寻宝游戏
题目给出了判定一个点是否在多边形内的方法，由于这只与射线经过的边的奇偶性有关，因此考虑状压奇偶性。
设 \(f_{i, j, S}\) 表示当前位于点 \((i, j)\) ，宝藏和陷阱的奇偶性为 \(S\) 的最短移动次数，大力 Bfs 转移即可。
code
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int max1 = 20;
const int inf = 1e8;
const int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };
int n, m, k;
char mp[max1 + 5][max1 + 5];
int px[max1 + 5], py[max1 + 5], val[max1 + 5];
int f[max1 + 5][max1 + 5][1 << 8];
struct Point
{
int x, y, S;
Point () {}
Point ( int __x, int __y, int __S )
{ x = __x, y = __y, S = __S; }
};
queue <Point> que;
int main ()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
scanf("%s", mp[i] + 1);
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= m; j ++ )
{
if ( mp[i][j] >= '0' && mp[i][j] <= '9' )
{
++k;
px[mp[i][j] - '0'] = i;
py[mp[i][j] - '0'] = j;
}
}
}
for ( int i = 1; i <= k; i ++ )
scanf("%d", &val[i]);
Point p;
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= m; j ++ )
{
if ( mp[i][j] == 'B' )
{
++k;
px[k] = i;
py[k] = j;
val[k] = -inf;
}
if ( mp[i][j] == 'S' )
p = Point(i, j, 0), que.push(p);
}
}
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
for ( int S = 0; S < (1 << k); S ++ )
f[i][j][S] = inf;
f[p.x][p.y][p.S] = 0;
while ( !que.empty() )
{
int x = que.front().x, y = que.front().y, S = que.front().S;
que.pop();
for ( int i = 0; i < 4; i ++ )
{
int nx = x + dx[i], ny = y + dy[i];
if ( nx < 1 || nx > n || ny < 1 || ny > m || (mp[nx][ny] != '.' && mp[nx][ny] != 'S') )
continue;
int nS = S;
if ( i < 2 )
{
for ( int j = 1; j <= k; j ++ )
if ( min(x, nx) == px[j] && py[j] > ny )
nS ^= 1 << (j - 1);
}
if ( f[nx][ny][nS] == inf )
{
f[nx][ny][nS] = f[x][y][S] + 1;
que.push(Point(nx, ny, nS));
}
}
}
int ans = 0;
for ( int S = 0; S < (1 << k); S ++ )
{
if ( f[p.x][p.y][S] == inf )
continue;
int up = -f[p.x][p.y][S];
for ( int i = 1; i <= k; i ++ )
up += ((S >> (i - 1)) & 1) * val[i];
ans = max(ans, up);
}
printf("%d\n", ans);
return 0;
}
T3 点分治
发现需要求解的就是本质不同的点分树的数量，没有办法根据删点的过程划分子问题，因此考虑最朴素的树形 dp 。
考虑一条边 \((u, v)\) ，如果我们已经得到 \(u, v\) 子树形成的点分树，考虑进行合并。
考虑合并后的点分树的根节点，容易发现这只能是 \(u\) 子树点分树的根节点或 \(v\) 子树点分树的根节点，如果根节点为 \(u\) 子树点分树的根节点，容易发现 \(u\) 子树点分树根节点中除 \(u\) 节点所在子树的其余儿子，一定为当前根节点的儿子，因此将这些部分删去，剩余部分仍然为两棵点分树，可以直接递归进行合并。容易发现 \(u\) 或 \(v\) 节点被删去后合并终止。
发现合并过程产生的贡献只与 \(u, v\) 节点在点分树中的深度有关，因此设 \(f_{u, i}\) 表示以 \(u\) 为根的子树， \(u\) 节点在点分树中的深度为 \(i\) 的方案数。转移考虑 \(u, v\) 节点哪个先被删去，如果 \(u\) 先被删去，枚举 \(v\) 点分树中在 \(u\) 之前被删去的深度进行转移； \(v\) 节点先被删去同理。简单优化可以做到 \(O(n^2)\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int max1 = 5000;
const int mod = 1e9 + 7;
int n;
vector <int> edge[max1 + 5];
int C[max1 + 5][max1 + 5];
int siz[max1 + 5], f[max1 + 5][max1 + 5], tmp[max1 + 5], sum[max1 + 5];
void Dfs ( int now, int fa )
{
siz[now] = 1;
f[now][1] = 1;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Dfs(v, now);
memcpy(tmp + 1, f[now] + 1, sizeof(int) * siz[now]);
memset(f[now] + 1, 0, sizeof(int) * (siz[now] + siz[v]));
sum[siz[v] + 1] = 0;
for ( int i = siz[v]; i >= 1; i -- )
sum[i] = (sum[i + 1] + f[v][i]) % mod;
for ( int i = 1; i <= siz[now]; i ++ )
for ( int k = 1; k <= siz[v]; k ++ )
f[now][i + k - 1] = (f[now][i + k - 1] + 1LL * tmp[i] * C[i - 1 + k - 1][i - 1] % mod * sum[k]) % mod;
for ( int j = 1; j <= siz[v]; j ++ )
{
sum[0] = 0;
for ( int i = 1; i <= siz[now]; i ++ )
sum[i] = (sum[i - 1] + C[i - 1 + j - 1][j - 1]) % mod;
for ( int i = 1; i <= siz[now]; i ++ )
f[now][i + j] = (f[now][i + j] + 1LL * tmp[i] * f[v][j] % mod * sum[i]) % mod;
}
siz[now] += siz[v];
}
return;
}
int main ()
{
freopen("dianfen.in", "r", stdin);
freopen("dianfen.out", "w", stdout);
scanf("%d", &n);
for ( int i = 2, u, v; i <= n; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
C[0][0] = 1;
for ( int i = 1; i <= n; i ++ )
{
C[i][0] = 1;
for ( int j = 1; j <= i; j ++ )
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
Dfs(1, 0);
int ans = 0;
for ( int i = 1; i <= n; i ++ )
ans = (ans + f[1][i]) % mod;
printf("%d\n", ans);
return 0;
}