Day8

比赛

T1

树的直径，把边长先处理出来即可

#include<bitsdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int maxn = 100005;
int v[maxn], fa[maxn];
struct edge
{
    int to, nxt, w;
}ed[maxn << 1];
int head[maxn], cnt;
inline void add(int u, int v, int w)
{
    ed[++ cnt] = {v, head[u], w}, head[u] = cnt;
    ed[++ cnt] = {u, head[v], w}, head[v] = cnt;
}
int res, d1[maxn], d2[maxn];
void dfs(int u, int fa)
{
    d1[u] = d2[u] = 0;
    for(int i = head[u]; i; i = ed[i].nxt)
    {
        int v = ed[i].to;
        if(v == fa)continue;
        dfs(v, u);
        int d = d1[v] + ed[i].w;
        if(d1[u] < d)d2[u] = d1[u], d1[u] = d;
        else if(d > d2[u])d2[u] = d;
    }
    res = max(res, d1[u] + d2[u]);
}
int main()
{
	//freopen("a_1.in", "r", stdin);
    int n = read();
    for(int i = 1; i <= n; ++ i)
    {
        v[i] = read();
    }
    for(int i = 2; i <= n; ++ i)
    {
        fa[i] = read();
        add(i, fa[i], v[i] ^ v[fa[i]]);
    }
    dfs(1, 0);
    cout << res << '\n';
    return 0;
}

T2

80分，先top排序，然后从后向前做dp

#include<bitsdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int maxn = 50005;
struct edge
{
    int to, nxt;
}ed[maxn];
int head[maxn], cnt, rd[maxn], st[maxn];
inline void add(int u, int v)
{
    ed[++ cnt] = {v, head[u]}, head[u] = cnt;
}
queue<int> q;
int n, m;
inline void topp()
{
    for(int i = 1; i <= n; ++ i)if(rd[i] == 0)q.push(i);
    int tt = 0;
    while(!q.empty())
    {
        int s = q.front();
        q.pop();
        //cout << s << '\n';
        st[++ tt] = s;
        for(int i = head[s]; i; i = ed[i].nxt)
        {
            int v = ed[i].to;
            -- rd[v];
            if(!rd[v]) q.push(v);
        }
    }
}
int dp[maxn];
int c(int t)
{
    int ans = 0;
    memset(dp, 0, sizeof dp);
    dp[t] = 1;
    for(int i = n; i >= 1; -- i)
    {
        int u = st[i];
        for(int j = head[u]; j; j = ed[j].nxt)
        {
            int v = ed[j].to;
            dp[u] += dp[v];
        }
    }
    for(int i = 1; i <= n; ++ i)ans += (dp[i] & 1) == 1;
    return ans;
}
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; ++ i)
    {
        int u = read(), v = read();
        add(u, v);
        ++ rd[v];
    }
    topp();
    int res = 0;
    for(int i = 1; i <= n; ++ i)
    {
        res += c(i);
    }
    cout << res - n;
    return 0;
}

100分因为只关心奇偶性

所以将转移中的加法变为异或

bitset维护

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
queue<int> q;
const int N = 50005;
bitset<N> dp[N];
int rd[N], m, n, st[N];
struct edge
{
	int to, nxt;
}ed[N << 1];
int cnt, head[N];
ll ans;
inline void add(int u, int v)
{
	ed[++ cnt] = {v, head[u]}, head[u] = cnt;
}
inline void topsort()
{
	queue<int> Q;
    for(int i = 1; i <= n; ++ i)if(rd[i] == 0)Q.push(i);
    int tt = 0;
    while(!Q.empty())
    {
        int s = Q.front();
        Q.pop();
        //cout << s << '\n';
        st[++ tt] = s;
        for(int i = head[s]; i; i = ed[i].nxt)
        {
            int v = ed[i].to;
            -- rd[v];
            if(!rd[v]) Q.push(v);
        }
    }
}
int main() {
	n = read(), m = read();
	for(int i = 1; i <= m; ++i)
	{
		int u = read(), v = read();
        add(u, v);
	}
	for(int i = 1;i <= n; ++i)
	{
		dp[i][i] = 1;
	}
	for(int i = 1; i <= n; ++ i)
	{
		int u = st[i];
		ans += dp[u].count() - 1;
		for(int i = head[u]; i; i = ed[i].nxt)
		{
			dp[ed[i].to] ^= dp[u];
		}
	}
	cout << ans << '\n';
	return 0;
}

T3

二分答案 $mid$, 检查是否存在合法的方案使根节点答案大于等于 $mid$。

设 $f[x]$ 表示最少在 $x$ 的子树里分配多少个大于等于 $mid$ 的叶子权值，使得 $x$ 的权值大于等于 $mid$。选择 $k / 2$ 个儿子节点，那么 $f[x] = \sum f[y]$,将儿子按 $f[x]$ 排序，从小到大选择，最终判断 $f[x]$ 是否等于可分配的叶子权值个数

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
#define N 200005
using namespace std;
int n, k, ans
int L = 1, R;
int head[N], ecnt;
int a[N];
struct edge
{
    int to, nxt;
}ed[N << 1];
ll dp[N];
inline void add(int u, int v)
{
    ed[++ ecnt] = {v, head[u]}, head[u] = ecnt;
}
void dfs(int u,int x){
    if(u >= n - k + 1)
    {
        if(a[u])
        {
            if(a[u] >= x) dp[u] = 0;
            else dp[u] = 0x3f3f3f3f;
        } 
        else dp[u]  = 1;
        return;
    }
    vector<ll> t;
    for(int i = head[u]; i ; i = ed[i].nxt)
    {
        int v = ed[i].to;
        dfs(v, x);
        t.push_back(dp[v]);
    }
    sort(t.begin(), t.end());
    int k = (int)t.size() / 2 + 1;
    for(int i = 0; i < k; ++ i)dp[u] += t[i];
}

bool check(int x)
{
    int d = k - x + 1;
    for(int i = n- k + 1 ; i <= n; ++ i)if(a[i] >= x) -- d;
    memset(dp, 0, sizeof dp);
    dfs(1, x);
    return d >= dp[1];
}
int main()
{
    n = read(), R = k = read();
    for(int i = 2; i <= n; ++ i)
    {
        add(read(), i);
    }
    for(int i = n - k + 1; i <= n; ++ i) a[i] = read();
    while(L <= R)
    {
        int mid = (L + R) >> 1;
        if(check(mid))ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << ans;
    return 0;
}

T4

考虑从上到下分配集合，或者按 $DFS$ 序分配，保证祖先在自己之前分配到集合中即可

那么有 $#include<bits/stdc++.h>

define ll long long

define ull unsigned long long

define gt getchar

using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}

define mod 1000000007

define N 100005

int cnt, m, n, dp[N][105];
struct edge
{
int to, nxt;
}ed[N << 1];
void add(int u, int v)
{
ed[++ cnt] = {v, head[u]}, head[u] = cnt;
}
void dfs(int u,int dep)
{
++ cnt;
for(int i = dep; i <= m; ++ i)
{
dp[cnt][i] = (1ll * dp[cnt - 1][i] * (i - dep + 1) + dp[cnt - 1][i - 1]) % mod;
}
for(int i = head[u]; i ; i = ed[i].nxt)dfs(to[i], dep + 1);
}
int main(){
n = read(), m = read();
dp[0][0] = 1;
for(int i = 2; i <= n; ++ i)
{
add(read(),i);
}
dfs(1, 1);
cout << dp[cnt][m];
return 0;
}f[x][y] = f[x - 1][y] \times (y - dep) + f[x + 1][y - 1]$

当 $y \ge dep$ 时，这代表放到之前的集合内(不能和祖先放在一起，其他的集合任意放)，或者自己新建一个集合

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
#define mod 1000000007
#define N 100005
int cnt, m, n, dp[N][105];
struct edge
{
	int to, nxt;
}ed[N << 1];
void add(int u, int v)
{
	ed[++ cnt] = {v, head[u]}, head[u]  = cnt;
}
void dfs(int u,int dep)
{
    ++ cnt;
    for(int i = dep; i <= m; ++ i)
	{
		dp[cnt][i] = (1ll * dp[cnt - 1][i] * (i - dep + 1) + dp[cnt - 1][i - 1]) % mod;
	}
    for(int i = head[u]; i ; i = ed[i].nxt)dfs(to[i], dep + 1);
}
int main(){
    n = read(), m = read();
    dp[0][0] = 1;
    for(int i = 2; i <= n; ++ i)
	{
        add(read(),i);
    }
    dfs(1, 1);
    cout << dp[cnt][m];
    return 0;
}

讲课

P1144最短路计数

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1 - N$ 问从顶点 $1$ 开始，到其他每个点的最短路有几条。$1 \le N \le 10^6, 1 \le 2 \times 10^6$。

考虑在求最短路时，设 $d[x]$ 表示最短路， $f[x]$ 表示最短路的条数。当更新最短路时， $d[y] = d[x] + 1, f[y] = f[x]$，否则如果最短路相同 $f[y] += f[x]$。

P3304 [SDOI2013] 直径

现在小Q想知道，对于一颗给定的树，其直径长度是多少，以及有多少条边满足所有直径都经过该边。$2 \le N \le 200000$。
考虑先求出一条直径，然后考虑其他直径和此直径分叉的地方，正反两遍 dfs 算出哪些地方可以分叉。

P3177 树上染色

有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0-n$ 之内的正整数，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他的点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。$1 \le n,k \le 2000$ 。

我们可以将路径拆分成边，就可以计算每条边被经过的次数。设 $dp_{x,y}$ 表示 $x$ 的子树内选了 $y$ 个黑点时，最优情况下子树内所有边的贡献和，考虑转移。假设有子树 $z$，考虑 $(x,z)$ 这条边的贡献，令 $z$ 里面黑点个数为 $t$，那么贡献为 $t(k-t)+(siz_z-t)(n-siz_t-k+t)$，背包转移即可。

P3174 [HAOI2009] 毛毛虫

对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就像一个毛毛虫，点数越多，毛毛虫就越大。$N\le 300000$。

设 $dp_x$ 表示从 $x$ 开始到子树内延伸的最长毛毛虫（不考虑 $x$ 上方节点），那么有转移：$dp_x=\max f_y+1+cnt_x-1$ ，其中 $y$ 是 $x$ 的儿子，$cnt_x$ 表示儿子的数量。最后枚举毛毛虫主链的中转点，合并两条半截的毛毛虫即可（记录 $x$ 点最大的两个 $f_y$）。

CF1153D Serval and Rooted Tree

$n$ 个节点以 $1$ 为根的一棵树，每个非叶子节点都有一个操作 $\max$ 或 $\min$（$0$ 表示 $\min$，$1$ 表示 $\max$），表示这个节点中的值应该分别等于其子节点中所有值的最大值或最小值。假设树上有 $k$ 个叶节点，你可以将每个叶节点填上 $[1,k]$ 的数字，且每个数字只使用一次，求根节点的最大值。

考虑设 $dp_x$ 表示只考虑其子树内叶节点的子问题，$x$ 的最大值是多少。
如果是 $\max$ 操作，找到 $siz_y-dp_y$ 最小的子树，那么 $dp_x=siz_x-siz_y+dp_y$，我们给 $y$ 的子树分配叶子中的最大值即可。如果是 $\min$ 操作，那么，对于每个子树都分配 $siz_y-dp_y+1$个大值。

P3523 [POI2011] DYN-Dynamite

给一棵树，树上有一些关键节点，要求你选 $m$ 个点，第 $i$ 个关键节点到这些点中每个点距离的最小值记为 $dis_i$，记这全部 $dis$ 的最大值为 $K$，现在要使 $K$ 最小，求这个 $K$。

考虑二分答案，那么选择一个点可以覆盖距离到其小于等于 $k$ 的所有关键点，检查是否可以完全覆盖整棵树。换个想法：求最少用多少点覆盖到所有的关键点。
设 $f_x$ 表示以 $x$ 受子树内选择点影响，最远可以向外覆盖多少，$g_x$ 表示以 x 为子树内最远还没有被覆盖到的关键点距离。那么如果 $g_x\le f_x$, 那么可以覆盖子树内所有点。如果 $g_x\ge mid$，那么必须在 $x$ 处新建选择点。

P1453 城市环路

整个城市可以看做一个 $n$ 个点，$m$ 条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 $2$ 个点不能同时开店，每个点都有一定的人流量，第 $i$ 个点的人流量是 $p_i$，在该点开店的利润就等于 $p_i\times k$，其中 $k$ 是一个常数。Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？
$n\le 10^5$ ，$1\le p_i\le 10^4$ ，$0\le u,v\le n$ ，$k\le 10^4$，$k$ 的小数点后最多有 $6$ 位数字。
对于树来说，发现就是求最大独立集，设 $f_{x,0/1}$ 表示 $x$ 点选或不选的最大值。对于环来说，考虑断环为链，相邻两个点一定有一个是不选，分别枚举强制某个点不选做一次链上的 DP 即可。

P4381 [IOI2008] Island

给出一个基环树森林（每一个点有一条无向边），有正边权，让你求出所有基环树的直径（即一条不经过重复点的基环树上的最长路径）之和。$2\le n\le 10^6$ 。

考虑求一个基环树的直径，先求出树的直径。对于环上的每个点，我们考虑记录 $f_x$ 表示从 $x$ 开始到其子树内最长路径是多少。断环为链，记录链上的路径前缀和，那么答案就是 $\max(f_i+f_j+s_j-s_i),\max(f_i+f_j+len-(pre_j-pre_i))$，代表走环的两部分。直接扫一遍即可。

CF1187E Tree Painting

给定一棵 $n$ 个点的树初始全是白点，要求你做 $n$ 步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点。求可获得的最大权值.

枚举第一次选的点 $x$，那么剩下的部分所获取的权值是固定的。以 $x$ 为根，答案为 $\sum siz_i$, $siz$ 为子树大小。换根 DP，先选定 $1$ 为根，考虑其他节点答案。由父亲的答案推儿子的答案。那么有 $dp_y=dp_x+n-2\times siz_y$。

P2986 [USACO10MAR] Great Cow Gathering G

每个奶牛居住在 $N$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $a_i$ 和 $b_i$，长度为 $L_i$。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C-i$ 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$，那么总路程就是 $C_i\times 20$）。帮助 Bessie 找出最方便的地点来举行大集会。
$1\le N\le 10^5$，$1\le a_i,b_i\le N$ ，$0\le C_i,L_i\le 10^3$ 。

换根 DP，选定 $1$ 号点为根，可以方便的计算出答案。
考虑由父亲的答案推儿子的答案，发现就是子树内少走了一段，子树外多走了一段。$dp_y=dp_x-sum_y\times w+(sum-sum_y)\times w$，$sum$ 表示所有 $C_i$ 的和，$sum_y$ 表示 $y$ 子树内 $c_i$ 的和，$w$ 是 $x$ 到 $y$ 的边权。

P4438 [HNOI/AHOI2018] 道路

给你一颗二叉树, 每个叶子节点 $i$ 有三个属性 $a_i,b_i,c_i$, 每个非叶子节点都能标记往左右儿子的边中的一条边((分别记为 $L$ 边和 $R$ 边))
设叶子节点 $i$ 到根的路径上没有被标记的 $L$ 边有 $x$ 条,$R$ 边有 $y$ 条，那么 $i$ 贡献就是 $c_i(a_i+x)(b_i+y)$，最小化所有点的贡献和，树的深度不超过 $40$。

设 $dp_{x,i,j}$ 表示从根到 $x$ 有 $i$ 条没有被标记的 $L$ 边和 $j$ 条没被标记的 $R$ 边，其子树内的代价和。对于叶子节点 $dp_{x,i,j}=c_x(a_x+i)(b_x+j)$。对于非叶子节点，枚举标记哪条边：$dp_{x,i,j}=\min(dp_{ls,i+1,j}+dp_{rs,i,j},dp_{ls,i,j}+dp_{rs,i,j+1})$，答案就是 $f_{1,0,0}$。

P2014 [CTSC1997] 选课

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？
( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ )

设 $dp_{x,i} $表示 $x$ 子树内选了 $i$ 门功课的最大学分。$dp_{x,i}=\max(dp_{x,j-k}+dp_{y,k})$，注意 $j-k\le siz_x,k\le siz_y$，可保证复杂度 $O(n^2)$。

LOJ 160. 树形背包

有 $N$ 个物品，编号分别为 $1...N$。物品 $i$ 的重量为 $w_i$，价值为 $v_i$。给出每个物品依赖于哪个物品。我们用 $d_i=j(i>j>0)$ 表示：如果要选取物品 $i$，就必须先选取物品 $j$。另外，我们用 $d_i=0(i>0)$ 表示：该物品不依赖于任何物品。保证每个物品最多只依赖一个物品。保证依赖关系合理，不会出现环。背包最多能装载的重量为 $W$，请问背包中最多能装入多大价值的物品。

dfn 序优化背包，按 dfn 序做背包，先递归子树，再计算自己。
那么如果不选自己，就不能选子树。
如果 $j\ge w_i,dp_{i,j}=\max(dp_{i-1,j-w+i}+v_i,dp_{i-siz_i,j})$，否则 $dp_{i,j}=dp{i-siz_i,j}$。