题面在代码中

A. 平衡

和昨晚的美团笔试差不多，先一遍dfs处理以sz[i], 得到以 i 为根的子树大小，枚举边求答案即可。

/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>

#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()

using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;

struct Edge {
  int u, v;
} edge[1000005];
vi G[1000005];
int sz[1000005];
void dfs(int u, int par) {
  sz[u] = 1;
  for (auto v : G[u]) {
    if (v == par) {
      continue;
    }
    dfs(v, u);
    sz[u] += sz[v];
  }
}
int ans[1000005], fa[1000005];
void solve() {
  int n;
  std::cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
    edge[i].u = u, edge[i].v = v;
    fa[u] = v;
  }
  int root = 1;
  for (int i = 1; i <= n; i++) {
    if (!fa[i]) {
      root = i;
    }
  }
  dfs(root, 0);
  int res = 1e9;
  for (int i = 1; i <= n - 1; i++) {
    int u = edge[i].u, father = edge[i].v;
    int now = std::abs(sz[u] - (n - sz[u]));
    ans[now]++;
    res = std::min(res, now);
  }
  std::cout << res << ' ' << ans[res] << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
/*
平衡
时间限制： 1000MS
内存限制： 65536KB
题目描述：
输入一棵树 T，你需要删除一条边，这棵树会被分成A 和 B 两棵树。你需要让两部分的节点数的差的绝对值| |A|-|B| |尽可能小。输出最小的| |A|-|B| |和最优方案的数量。



输入描述
第一行一个整数 n表示节点的数量，节点从1 到 n编号。

接下来n-1行每行两个正整数 s t，表示s的父亲是t。

输入保证是一棵树。

对于所有数据 1<=n<=100000。

输出描述
输出一行，两个整数，用空格分开，分别表示最优解和最优方案数。


样例输入
3
2 1
3 1
样例输出
1 2
*/

B. 配制溶液

要配置体积为V的溶液，可以枚举子状态 i 和 V - i, 其实就是求子状态的最优策略，所以可以递归做，类似于记忆化搜索。

/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>

#define int long long
#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()

using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;

int A[1005], B[1005];
int dp[1005][1005];
int Max[1005], f[1005];
int n, X, C;

int dfs(int now) {
  if (f[now] != -1) {
    return f[now];
  }
  int ans = 0;
  for (int i = 1; i <= now - 1; i++) {
    if (!dfs(i) or !dfs(now - i)) {
      continue;
    }
    if (i == now - i) {
      ans = std::max(ans, dfs(i) + dfs(now - i) + X);
    } else {
      ans = std::max(ans, dfs(i) + dfs(now - i));
    }
  }
  return f[now] = std::max(Max[now], ans);
}
void solve() {
  memset(f, -1, sizeof(f));
  std::cin >> n >> X >> C;
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i];
  }
  for (int i = 1; i <= n; i++) {
    std::cin >> B[i];
    Max[A[i]] = std::max(Max[A[i]], B[i]);
  }
  for (int i = 1; i <= C; i++) {
    std::cerr << i << ' ' << dfs(i) << '\n';
  }

  std::cout << dfs(C) << '\n';
}

signed main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
/*
配制溶液
时间限制： 3000MS
内存限制： 589824KB
题目描述：
实验室需要配制一种溶液。现在，研究员面前有n种该物质的溶液，每一种有无限多瓶，第i种的溶液体积为xi，里面含有yi单位的该物质。研究员每次可以选择一瓶溶液，将其倒入另外一瓶（假设瓶子的容量无限），即可以看作将两个瓶子内的溶液合并。此时合并的溶液体积和物质含量都等于之前两个瓶子内的之和。

特别地，如果瓶子A与B的溶液体积相同，那么A与B合并之后该物质的含量会产生化学反应，使得该物质含量增加X单位。

研究员的任务是配制溶液体积恰好等于C的，且尽量浓的溶液（即物质含量尽量多）。研究员想要知道物质含量最多是多少。



输入描述
第一行三个正整数n,X,C；

第二行n个正整数x1,x2,...,xn，中间用空格隔开；

第三行n个正整数y1,y2,...,yn，中间用空格隔开。

对于所有数据，1≤n,X,C,yi≤1000,1≤xi≤C

数据保证至少存在一种方案能够配制溶液体积恰好等于C的溶液。

输出描述
输出一行一个整数，表示答案。


样例输入
3 4 16
5 3 4
2 4 1
样例输出
29
*/

C. 双色球

有个小坑：当红球在袋子里的时候，每过去一秒上面的数字就会增加1，蓝球上的数字则会减少1。

一开始没注意到，wa了很多次。我们只需要记录当前放了多少个红和蓝，记录编号为id的小球放进去的时间就可以了。

/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>

#define int long long


#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()

using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;

int A[500005], B[1000005], C[1000005], in[1000005];
std::string color;

void solve() {
  int n;
  while (std::cin >> n) {
  //std::cin >> n;
  i64 sum = 0;
  int red = 0, blue = 0;
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i];
  }
  std::cin >> color;
  color = ' ' + color;
  int m;
  std::cin >> m;
  for (int i = 1; i <= m; i++) {
    std::cin >> B[i];
  }
  for (int i = 1; i <= m; i++) {
    std::cin >> C[i];
  }
  for (int i = 2; i <= m; i++) {
    assert(B[i] > B[i - 1]);
  }
  int Nowtime = 0;
  memset(in, -1, sizeof(in));
  std::vector<i64> ans;
  for (int i = 1; i <= m; i++) {
    int TimeDet = B[i] - Nowtime;
    sum += red * TimeDet;
    sum -= blue * TimeDet;
    if (C[i] == 0) {
      ans.emplace_back(sum);
    } else {
      int id = std::abs(C[i]);
      if (C[i] > 0) {
        assert(in[id] == -1);
        sum += A[id];
        in[id] = B[i];
        red += color[id] == 'R';
        blue += color[id] == 'B';
      } else if (C[i] < 0) {
        sum -= A[id];
        sum -= (color[id] == 'R' ? 1 : -1) * (B[i] - in[id]);
        A[id] = (A[id] + (color[id] == 'R' ? 1 : -1) * (B[i] - in[id]));
        red -= color[id] == 'R';
        blue -= color[id] == 'B';
        in[id] = -1;
      }
    }
    //std::cerr << i << ' ' << sum << '\n';
    Nowtime = B[i];
  }
  std::cout << ans.size();
  for (auto iter : ans) {
    std::cout << ' ' << iter;
  }
  std::cout << '\n';
  }
}

signed main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
/*
 
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小明有一个神奇的袋子和一堆编号为1到n的球。每个球都被涂成了红色或者蓝色，且这些球的表面上都分别写着一个数字。

当红球在袋子里的时候，每过去一秒上面的数字就会增加1，蓝球上的数字则会减少1。

小明会时不时向袋子里放入球或取出球，并且他想知道某些时刻袋子中球上写的数字之和。



输入描述
第一行有一个正整数n(1<=n<=5000)，代表小明有几个球。

第二行有n个范围在[-1000000,1000000]内的整数，第i个代表编号为1到n的球上写的数。

第三行是一个长度为n的仅由`R`和`B`构成的字符串，第i个字母代表编号为i的球是红色(R)或蓝色(B)

第四行有一个正整数m(1<=m<=100000)，代表小明进行了几次操作。

第五行有m个递增的正整数，第i个代表小明进行的第i次操作时间点。每个时间点小明只会进行至多一次操作。时间点的范围在[1,1000000000]内。

第六行有m个整数，第i个代表小明进行的操作。0为询问当前时间点袋中球上的数字之和，正数x代表放入了编号为x的球，负数-x代表取出了编号为x的球。

最开始袋子是空的。 你可以认为球上的数字变化均发生在时间点之前，而每次操作均发生在时间点之后。输入保证操作合法。

输出描述
设小明进行了k次询问。你需要在一行中先输出k，然后输出k个数，第i个代表第i次询问的答案。

题目保证小明进行过至少一次询问。


样例输入
3
-5 4 6
RBR
9
1 2 3 4 5 6 8 13 14
1 3 0 2 -3 0 -1 0 -2
样例输出
3 4 2 -5

3
1 1 1
RRB
4
1 2 3 10
1 3 -1 0
*/