更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369112

思路

要求满足不回家的人和外校的人都有床睡，一个人只会睡自己认识的人的床。

考虑二分图最大匹配。

然后，这个点 $u \to v$ 连边的前置条件是 $v$ 是在校学生，且 $v$ 回家睡觉。

需要注意的是，自己显然是可以睡自己的床的（并非废话），只要这个学生在校且不回家，就可以 $u \to u$。

将图建出来之后，直接跑二分图最大匹配即可。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 55;
int n;
int T;
bool at[MAXN];
int home[MAXN];
vector<int> g[MAXN];
int mac[MAXN];
bool vis[MAXN];

bool dfs(int u){
	for(int &v : g[u]){
		if(!vis[v]){
			vis[v] = 1;
			if(mac[v] == -1 || dfs(mac[v])){
				mac[v] = u;
				return true;
			}
		}
	}
	return false;
}

int hungary(int n){
	int cnt = 0;
	memset(mac, -1, sizeof(mac));
	for(int i = 1;i <= n;i ++){
		memset(vis, 0, sizeof(vis));
		if(!at[i] || (at[i] && !home[i])) cnt += dfs(i);
	}
	return cnt;
}

int main(){

	cin >> T;

	while(T --){
		int sum = 0;
		cin >> n;
		for(int i = 1;i <= n;i ++) g[i].clear();
		for(int i = 1;i <= n;i ++){
			cin >> at[i];
		}
		for(int i = 1;i <= n;i ++){
			cin >> home[i];
			if(!home[i] && at[i]){
				g[i].push_back(i);
			}
        }
        for(int i = 1;i <= n;i ++){
            if(!at[i] || (at[i] && !home[i])) sum ++;
        }
		for(int i = 1;i <= n;i ++){
			for(int j = 1;j <= n;j ++){
				bool rela; cin >> rela;
				if(rela && at[j]){
					g[i].push_back(j);
				}
			}
		}
		if(hungary(n) == sum){
			cout << "^_^\n";
		}
		else{
			cout << "T_T\n";
		}
	}


	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19343265

思路

首先考虑用线段树做。

发现数据范围很大，但是实则不需要考虑啊，因为我们的海报的数量一定，可以考虑离散化去重，然后用线段树做。

每次更改一段区间的话，采用标记延迟下传的方式，如果在目标区间就先打上懒标记，如果以后访问到了再下传，这样就不必要每次放到叶子上了。

最终查询就直接访问所有叶子就好，用个 set 去重海报。

代码

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

const int N = 1e6 + 10;

int a[N], lazy[N], n, c;

set<int> cnt;

void update(int rt, int l, int r, int L, int R, int x) {
    if (L > r || R < l) return;
    if (L <= l && r <= R) {
        lazy[rt] = x;
        a[rt] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    update(rt * 2, l, mid, L, R, x);
    update(rt * 2 + 1, mid + 1, r, L, R, x);
}

void query(int rt, int l, int r) {
    if (l == r) {
        if (a[rt]) cnt.insert(a[rt]);
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    query(rt * 2, l, mid);
    query(rt * 2 + 1, mid + 1, r);
}

int l[N], r[N];

int main() {
    int c;
        cin >> c >> n;
        memset(a, 0, sizeof(a));
        memset(lazy, 0, sizeof(lazy));
        set<int> uniq;
        map<int, int> d;
        for (int i = 1; i <= n; i++) {
            cin >> l[i] >> r[i];
            uniq.insert(l[i]);
            uniq.insert(r[i]);
            uniq.insert(l[i] - 1);
            uniq.insert(r[i] + 1);
        }
        int now = 0;
        for (auto x: uniq) {
            d[x] = ++ now;
        }
        for (int i = 1; i <= n; i++) {
            l[i] = d[l[i]];
            r[i] = d[r[i]];
            update(1, 1, now, l[i], r[i], i);
        }
        cnt.clear();
        query(1, 1, now);
        cout << cnt.size() << endl;

    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

思路

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。

代码

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 3e5 + 5;
const int LOG = 18;

struct node{
    int to, nxt;
}e[MAXN * 2];

int h[MAXN], tot;
int T, n;
int son1[MAXN], son2[MAXN];
int f[MAXN], up[MAXN][LOG + 1];
int son3[MAXN];
int fu[MAXN];
int sz[MAXN], csz[MAXN];
long long ans;

void add(int x, int y){
	e[++ tot] = {y, h[x]};
    h[x] = tot;
}

void dfs1(int u, int fa){
    sz[u] = 1;
    f[u] = fa;
    son1[u] = son2[u] = 0;
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son1[u]]){
            son2[u] = son1[u];
            son1[u] = v;
        }
        else if(sz[v] > sz[son2[u]]){
            son2[u] = v;
        }
    }
    up[u][0] = son1[u];
    for(int i = 1;i <= LOG;i ++){
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
}

int check(int x, int sum, int maxx){
    if(!x) return 0;
    return (max(maxx, sum - csz[x]) <= sum / 2) ? x : 0;
}

void dfs2(int u, int fa){
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        //处理大子树u
        csz[u] = n - sz[v];
        son3[u] = (son1[u] == v) ? son2[u] : son1[u];
        if(fa && csz[fa] > csz[son3[u]]) son3[u] = fa;
        up[u][0] = son3[u];
        for(int j = 1;j <= LOG;j ++){
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        int hav1 = u;
        for(int j = LOG;j >= 0;j --){
            if(csz[u] - csz[up[hav1][j]] <= csz[u] / 2){
                hav1 = up[hav1][j];
            }
        }
        ans += check(son3[hav1], csz[u], csz[son3[son3[hav1]]]);
        ans += check(hav1, csz[u], csz[son3[hav1]]);
        ans += check(fu[hav1], csz[u], csz[son3[fu[hav1]]]);
        //处理小子树v
        csz[v] = sz[v];
        int hav2 = v;
        for(int j = LOG;j >= 0;j --){
            if(csz[v] - csz[up[hav2][j]] <= csz[v] / 2){
                hav2 = up[hav2][j];
            }
        }
        ans += check(son1[hav2], csz[v], csz[son1[son1[hav2]]]);
        ans += check(hav2, csz[v], csz[son1[hav2]]);
        ans += check(fu[hav2], csz[v], csz[son1[fu[hav2]]]);
        //递归处理子节点，维护临时父方向
        fu[u] = v;
        dfs2(v, u);
        //恢复原状态
        son3[u] = son1[u];
        up[u][0] = son1[u];
        for(int j = 1;j <= LOG;j ++){
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        csz[u] = sz[u];
        fu[u] = f[u];
    }
    son3[u] = son1[u];
    up[u][0] = son1[u];
    for(int j = 1;j <= LOG;j ++){
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    csz[u] = sz[u];
    fu[u] = f[u];
}

void init(){
    tot = 0; ans = 0;
    memset(h, 0, sizeof(h));
    memset(son1, 0, sizeof(son1));
    memset(son2, 0, sizeof(son2));
    memset(son3, 0, sizeof(son3));
    memset(f, 0, sizeof(f));
    memset(fu, 0, sizeof(fu));
    memset(sz, 0, sizeof(sz));
    memset(csz, 0, sizeof(csz));
    memset(up, 0, sizeof(up));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
    while(T --){
        init();
		cin >> n;
        for(int i = 1;i < n;i ++){
            int u, v; cin >> u >> v;
            add(u, v), add(v, u);
        }
        dfs1(1, 0);
        memcpy(csz, sz, sizeof(sz));
        memcpy(son3, son1, sizeof(son1));
        memcpy(fu, f, sizeof(f));
        dfs2(1, 0);
        cout << ans << '\n';
    }
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359481

思路

首先，这个题目的建图太抽象了，需要好好理解一下。

然后我们考虑树上背包。

我们定义 $f_{u, j}$ 表示，在 $u$ 这颗子树内选择 $j$ 个叶子节点的最大收益（叶子点权和 $-$ 需要的边权和）。

那么我们显然有转移：

$ f_{u, j} = \max(f_{u, j}, f_{u, j - k} + f_{v, k} + w(u, v)) $

显然如果你选择了 $v$ 这个子树所产生的收益，那么你就必须承担 $u - v$ 这条边的代价。

然后随便作一些上下界优化即可。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 3005;
int n, m;
struct node{
	int u, w;
};
vector<node> e[MAXN];
int a[MAXN], sz[MAXN];
int f[MAXN][MAXN];

void dfs(int u){
	f[u][0] = 0;
	if(e[u].empty()){
		f[u][1] = a[u];
		return;
	}
	for(int i = 0;i < e[u].size();i ++){
		int v = e[u][i].u, w = e[u][i].w;
		dfs(v);
		for(int j = min(m, sz[u]);j >= 1;j --){
			for(int k = max(0, j - sz[u] - sz[v]);k <= min(j, sz[v]);k ++){
				f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - w);
			}
		}
	}
}

void dfs2(int u){
	sz[u] = 1;
	for(int i = 0;i < e[u].size();i ++){
		int v = e[u][i].u;
		dfs2(v);
		sz[u] += sz[v];
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(f, -0x3f3f3f3f, sizeof(f));
    cin >> n >> m;
    for(int i = 1;i <= n - m;i ++){
    	int k; cin >> k;
    	for(int j = 1;j <= k;j ++){
    		int c, w; cin >> c >> w;
    		e[i].push_back({c, w});
		}
	}
	for(int i = n - m + 1;i <= n;i ++){
		cin >> a[i];
	}
	dfs2(1);
	dfs(1);
    int ans = 0;
    for(int i = m;i >= 0;i --){
        if(f[1][i] >= 0){
            ans = i;
            break;
        }
    }
	cout << ans << '\n';
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359545

大意

求一颗树上，分离出来 $p$ 个点，使得其所需减少的边最小，求这个值。

思路

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。

代码

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 155;

struct node{
	int to, nxt;
}e[MAXN];
int sz[MAXN], n, p;
int h[MAXN], tot = 0;
void add(int x, int y){
	e[++ tot] = {y, h[x]};
	h[x] = tot;
}

int f[MAXN][MAXN];

void dfsz(int u, int fa){
	sz[u] = 1;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfsz(v, u);
		sz[u] += sz[v];
	}
	f[u][0] = 0;
	f[u][sz[u]] = 1;
}

int ans = 1e9;

void dfs(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		for(int j = sz[u] - 1;j >= 0;j --){
			for(int k = 0;k <= j;k ++){
				f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
	if(sz[u] - p >= 0){
        if(u == 1) ans = min(ans, f[u][sz[u] - p]);
        else ans = min(ans, f[u][sz[u] - p] + 1);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> p;

	for(int i = 1;i < n;i ++){
		int u, v; cin >> u >> v;
		add(u, v); add(v, u);
	}
	memset(f, 0x3f3f3f, sizeof(f));
	dfsz(1, 0);
	dfs(1, 0);
	cout << ans << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19373303

此题目前无 spj，遂 30 pts.

大意

$m$ 对关系 $(u, v)$，第 $i$ 对表示 $i$ 这个点可以选择 $u$ 或 $v$。求最大的选择题数的方案数和方案。

（如果一道题做不出来就无法进行下一道题目）

思路

考虑二分图最大匹配。

实则并不算最大匹配，我们通过读题可以发现其实就是二分图匹配的过程，每次找一条增广路，如果找不到了，就说明当前无法继续进行这个游戏了。

也就是在匹配的过程中记录答案，如果找不到增广路径，那就直接 break 即可。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 1e3 + 5;
int n, m;
int mac[MAXN], ans[MAXN];
bool vis[MAXN];
vector<int> g[MAXN];

bool dfs(int u){
	for(int &v : g[u]){
		if(!vis[v]){
			vis[v] = 1;
			if(mac[v] == -1 || dfs(mac[v])){
				ans[u] = v;
				mac[v] = u;
				return true;
			}
		}
	}
	return false;
}

int hungary(int n){
	int cnt = 0;
	for(int i = 1;i <= m;i ++){
		memset(vis, 0, sizeof(vis));
		if(dfs(i)){
			cnt += 1;
		}
		else{
			return cnt;
		}
	}
	return cnt;
}

int main(){
	cin >> n >> m;

	for(int i = 1;i <= m;i ++){
		int u, v; cin >> u >> v;
		g[i].push_back(u);
		g[i].push_back(v);
	}

	memset(mac, -1, sizeof(mac));
	int cnt = hungary(n);

	cout << cnt << '\n';
	for(int i = 1;i <= cnt;i ++){
		cout << ans[i] << '\n';
	}

	return 0;
}