A,B
直接模拟即可。
C
纵向的距离很好算。有两种情况：
-
横向距离更小。这个直接输出纵向距离。
-
更大。减去纵向的步数。
横向距离怎么算？我们考虑把 \(s,e\) 都移动到方块靠左，然后就是横坐标之和。
D
简单的 dp。设 \(dp_{i,msk}\) 为到了第 \(i\) 为，目前前面的状态是 \(msk\)，A,B 分别是 \(0,1\)。转移可以预处理也可以直接判断填 A,B 可不可以。
E
直接单调栈维护目前目前的最大值们。如果有更优（即更靠后切更大）就弹出。
F
考虑到知道每一个都至少有 \(1\)，树就是可以构造出来的，一共要分配 \(2n-2\)。我们先给每一个 \(1\)，然后优先队列贪心分配就可以了。
G
我一个很显然的数据分治（出现次数 \(<\sqrt{n}\) 的暴力，否则树上 dp），但是还要 \(\mathcal{O}(1)\) 的 lca，然后我不会。
其实这个题可以直接启发式合并。每一个节点维护每一个颜色的出现个数。可以把 \(+\) 和 \(-\) 分开来，这样好算。代码也很简单。
这道题按道理来说虚树，点分治都可以做，但是这个应该是我见到的最简洁的写法。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
int n,dep[N],a[N],fr[N];
vector<int> g[N];
map<int,int> mp[N];
ll ans;
void dfs(int u,int fa){
for (auto v : g[u]){
if (v^fa){
dep[v]=dep[u]+1;
dfs(v,u);
}
}
mp[u][a[u]]=1;
for (auto v : g[u]){
if (v^fa){
if (mp[v].size()>mp[u].size()){
swap(mp[v],mp[u]);
}
for (auto x : mp[v]){
ans-=1ll*x.second*mp[u][x.first]*dep[u]*2ll;
mp[u][x.first]+=x.second;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<n; i++){
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1; i<=n; i++){
cin>>a[i];
fr[a[i]]++;
}
dfs(1,0);
for (int i=1; i<=n; i++){
ans+=1ll*(fr[a[i]]-1)*dep[i];
}
cout<<ans<<"\n";
return 0;
}