T1.简单树（easy.cpp）
题目描述
给定一棵 n 个点的树，你需要给每条边赋值 0 或 1，求树上所有点对之间的简单路径权值总和的最大值，并输出方案。
一条路径的权值定义为这条路径上所有边权的异或和。
题解
引理
可以知道， ans(x,y) = ans(x, root) \oplus ans(y, root)。将树想象成一颗有根树，不管上面的路径是什么，当前节点跟父亲之间的路决定了 ans(root, now) ，我们设 a_i 为 ans(root, i)，显然这个 a 数组是可以自己决定的。
答案最大化
怎么让答案最大呢？设答案为\texttt 1的点有 x 个，答案为\texttt 0的点有 y 个，有x + y = n，则根据基本不等式，xy 的最大值在 x=y时。
根据点的数量和边的关系进行赋值即可。
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e6 + 10;
int n;
struct edge{int u, v;}G[N];
int a[N];
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int u, v;
scanf("%d", &n);
for(int i = 1; i <= n - 1; i++) {
scanf("%d%d", &u, &v);
G[i].u = u, G[i].v = v;
}
printf("%d\n", (n / 2) * (n - n / 2));
for(int i = 1; i <= n / 2; i++) a[i] = 0;
for(int i = n / 2 + 1; i <= n; i++) a[i] = 1;
for(int i = 1; i <= n - 1; i++) {
printf("%d ", a[G[i].u] != a[G[i].v]);
}
return 0;
}
T2.扑克（poker.cpp）
题目描述
你在玩德州扑克，现在手上有两张牌，桌上有三张牌，你要知道你是否必胜。
原题：
一副去掉大小王的扑克牌包含 13 种不同的数值：2,3,4,5,6,7,8,9,T,J,Q,K,A，它们的大小从左到右依次递增。扑克牌中有四种不同的花色，用 S,H,D,C 表示，每一种花色都有 13 张牌，分别对应每一种数值。在德州扑克中，我们只需要考虑这 52 张牌。
一副手牌包含 5 张扑克牌，他们可能会形成若干种牌型，按照从大到小的顺序依次为：
- 同花顺：花色相同的顺子（顺子的定义见下方），例如同花色的 T,J,Q,K,A。
- 四条：存在四张大小相同的牌，例如任意花色的 T,T,T,T,2。
- 葫芦：有三张牌大小相同，另外两张牌大小相同，例如任意花色的 T,T,T,J,J。
- 同花：五张牌花色相同，例如同花色的 7,J,Q,K,A。
- 顺子：五张牌大小连续，例如任意花色的 2,3,4,5,6, T,J,Q,K,A。特殊地，A,2,3,4,5 也是一个顺子（但是 K,A,2,3,4 不是）。因此一共有 10 种不同数值的顺子，它们的第一张牌分别是 A,2,3,4,5,6,7,8,9,T。
- 三条：存在三张大小相同的牌，例如任意花色的 T,T,T,J,Q。
- 两对：存在两个大小不同的对子（一个对子是两张大小一样的牌），例如任意花色的 T,T,Q,Q,K。
- 对子：存在两张大小相同的牌，例如任意花色的 T,T,J,Q,K。
- 高牌：不满足以上任何一个牌型的手牌都是高牌。
一副手牌可能同时满足很多个不同的牌型，这个时候我们会把最大的那个牌型作为这副手牌的牌型。
我们可以通过如下方式来比较两副手牌的大小：
- 如果两副手牌牌型不同，那么牌型较大的手牌更大。
- 如果两副手牌都是顺子或者都是同花顺，那么按照顺子第一张牌的大小排序，从小到大分别为 A,2,3,4,5,6,7,8,9,T，即 A,2,3,4,5 是最小的顺子，T,J,Q,K,A 是最大的顺子。
- 否则，我们按照（出现次数，数值）的双关键字从大到小把这五张牌排序，例如 K,K,T,T,T 排序后就是 T,T,T,K,K；2,T,T,K,A 排序后是 T,T,A,K,2。
- 比较两副牌的字典序。
- 注意，牌的花色只影响第一步比较牌型，并不影响后面两步的比大小。
手牌更大的玩家将获得胜利，如果两方的手牌一样大，则视为平局。
Haitang 在和 dXqwq 玩德州扑克。她们会先给每人发两张牌，再在桌面发三张牌，再进行一轮加注，再在桌面发两张牌，最后每个人在桌面的五张牌和自己的两张牌中组出最大的牌型，赢家拿走所有筹码。
dXqwq 是大聪明，所以她会用一个聪明的策略：如果在翻开桌面的三张牌之后，无论接下来翻开的牌和 Haitang 手里的牌是什么，她都能赢得胜利，她就会全押（all in），否则她就会过牌（check）或者弃牌（fold）。
虽然 dXqwq 很会博弈，但是她不会判定自己是否必胜。你需要帮助 dXqwq 完成这件事情。如果完成了，dXqwq 会将自己赢得的筹码分你一半。
不出意料地，dXqwq 过了一个小时便垂头丧气地来找你了：她把零花钱输光了。
对于每组数据，如果 dXqwq 必胜，输出 allin，否则输出 check。
题解
我们手中有两张固定的牌，对手手中还有其他牌。对于除了同花顺的牌型，对于牌型的花色要求都不是很高，所以对手可以拿出炸弹。考虑最大的炸弹AAAA，虽然我将 A 都拿光了，但对手依旧可以根据公共牌组出同花顺。所以只考虑同花顺的情况。
如果是同花顺，什么情况对手可以掏出更大的同花顺呢？
- Case1：公共牌有任意一张大于两张手牌，且对手可以用公共牌组同花顺，且手牌小于10
- Case2：公共牌有一张A，且这张A被我组同花顺
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
int T;
/*
只有同花才可以
前两个比后面的大，对手就无法构造
如果我是12345，必输
54321，必输
15234，必胜
*/
int dic[200];
int main()
{
freopen("poker.in", "r", stdin);
freopen("poker.out", "w", stdout);
scanf("%d", &T);
for(int i = 2; i <= 9; i++) {
dic[i + '0'] = i;
}
dic['A'] = 14;
dic['T'] = 10, dic['J'] = 11, dic['Q'] = 12, dic['K'] = 13;
char s1[5], s2[5], s3[5], s4[5], s5[5];
while(T--) {
scanf("%s%s%s%s%s", s1, s2, s3, s4, s5);
int t1 = dic[s1[1]], t2 = dic[s2[1]], r0 = dic[s3[1]], r1 = dic[s4[1]], r2 = dic[s5[1]];
int h1 = s1[0], h2 = s2[0], h3 = s3[0], h4 = s4[0], h5 = s5[0];
int flag = false;
if(h1 == h2 && h2 == h3 && h3 == h4 && h4 == h5) {
flag = true;
priority_queue<int> q;
q.push(t1); q.push(t2); q.push(r0); q.push(r1); q.push(r2);
int tp = q.top(); q.pop();
flag = true;
int maxx = tp;
while(!q.empty()) {
int tmp = q.top(); q.pop();
// printf("%d %d\n", tp, tmp);
if(abs_sub(tmp, tp) != 1) flag = false;//不连续
tp = tmp;
}
if(t1 < 10 && t2 < 10 && (t1 < r0 || t1 < r1 || t1 < r2) and (t2 < r0 || t2 < r2 || t2 < r1)) flag = false;
//有A，除了自己是最大
// else if(r0 == 14 || r1 == 14 || r2 == 14) flag = false;
}
if((t1 == 14 && t2 == 5) || (t1 == 5 && t2 == 14)) {
t1 = t1 == 14 ? 1 : 5, t2 = t2 == 14 ? 1 : 5;
priority_queue<int> q;
q.push(t1); q.push(t2); q.push(r0); q.push(r1); q.push(r2);
int tp = q.top(); q.pop();
flag = true;
while(!q.empty()) {
int tmp = q.top(); q.pop();
// printf("%d %d\n", tp, tmp);
if(abs_sub(tmp, tp) != 1) flag = false;//不连续
tp = tmp;
}
}
if(flag) printf("allin\n");
else printf("check\n");
}
return 0;
}
T7.故乡的老树（extree.cpp）
相同题目：CF686D/CF685B – Kay and Snowflake
题目描述
给出一颗以\texttt 1为根的树，求所有子树的重心编号，如果有多个，则按照节点编号从小到大输出。
题解
树的重心
在本题中，题目给出的信息是：到这颗子树所有点的距离之和最小的点，这个就是树的重心，但是如果不知道重心的其它性质，这个题目就不是绿题了……考虑到我现在还不会树剖，做这道题之前我还是不知道重心是什么的。
重心的性质：
- 以树的重心为根时，所有子树不超过整棵树大小的一半
- 树中所有点到重心的距离之和是最短的
- 一颗树中至多有两个重心，并且这两个重心一定是相连的
- 把两棵树通过一条边相连得到一颗新的树，那么新的树的重心在连接原来两个重心的路径上，且链为重链
- 在一颗树上添加一个点或者删除一个点，重心的位置最多移动一格
- 当某节点的重儿子的体积的两倍小于该节点的体积，该点为该颗树的重心
做法
有了上面你的性质，我们先递归到底层，叶子节点的重心就是自己，标记完之后，回溯。回溯了我们往上找父亲，直到找到一个重心。
关于是否是重心，判断可以用最后一条性质。
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e6 + 10;
int n, q;
struct edge{
int to, nxt;
}G[N << 1];
int head[N];
int cnt;
inline void init() {
for(int i = 1; i <= n; i++) {
head[i] = -1;
}
}
inline void add_edge(int u, int v) {
G[++cnt] = (edge){v, head[u]};
head[u] = cnt;
}
int siz[N], maxs[N], pre[N], ans[N][2];
inline void get_v(int pos, int fa) {
siz[pos] = 1, pre[pos] = fa;
for(int i = head[pos]; i != -1; i = G[i].nxt) {
if(G[i].to == fa) continue;
get_v(G[i].to, pos);
siz[pos] += siz[G[i].to];
if(siz[G[i].to] > siz[maxs[pos]]) maxs[pos] = G[i].to;
}
// printf("%d\n", pos);
}
inline bool check(int pos, int fa) {
return max(siz[maxs[pos]], siz[fa] - siz[pos]) * 2 <= siz[fa];
}
inline void dfs(int pos, int fa) {
if(!maxs[pos]) {ans[pos][0] = pos; return;}
for(int i = head[pos]; i != -1; i = G[i].nxt) {
if(G[i].to == fa) continue;
dfs(G[i].to, pos);
}
int preans = ans[maxs[pos]][0];
while(!check(preans, pos)) preans = pre[preans];
ans[pos][0] = preans;
if(preans != pos && check(pre[preans], pos)) {
ans[pos][1] = pre[preans];
if(ans[pos][0] > ans[pos][1]) swap(ans[pos][0], ans[pos][1]);
}
}
int main()
{
// freopen("extree2.in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d%d", &n, &q);
init();
int u, v;
for(int i = 2; i <= n; i++) {
scanf("%d", &u);
add_edge(u, i);
add_edge(i, u);
}
get_v(1, 0);
dfs(1, 0);
// for(int i = 1; i <= n; i++) {
// printf("%d: %d %d\n", i, maxs[i], siz[i]);
// }
int d;
for(int i = 1; i <= q; i++) {
scanf("%d", &d);
printf("%d ", ans[d][0]);
}
return 0;
}
