题意
通信题。Anya 和 Boris 有一棵有根树，每一天 Anya 会标记一些边，她可以给 Boris 发送一个不超过 1000 位的二进制串，Boris 要多次回答一个点到根的路径上有多少条边被标记过，他不知道这个二进制串，但是每次回答可以查看这个二进制串的 20 位。要求你给出两人的策略。
思路
很有意思的通信题，可能是受到了树分块的启发？
首先，Anya 要传递的肯定是每个点到根有多少条被标记的边，而直接传需要 \(n\log n\) 位，这是不能接受的。
因为是在一棵树上，我们尝试尽量多的继承祖先的信息来用更少的位来实现。这里体现了一点点树分块的思想，即标记一些关键点，然后把一个点到根的路径拆成这个点到最近的关键点和从关键点到根两部分。
具体地，我们把所有点按深度模 10 的余数分类，然后取其中数量最少的一类，把这些点标记为关键点。对于关键点，最多只有 50 个，我们记录这些点到根的路径上被标记的边的数量在二进制下的每一位，需要 9 位；对于非关键点，我们只记录这个点的父亲边是否被标记，需要 1 位。因此这一部分我们最多需要用 900 位。
对于 Boris，我们先从当前点往上跳，直到遇到一个关键点，这最多需要 9 次，然后我们查询这个关键点的信息，最多需要 9 次，于是我们就只需要最多询问 18 次来求出答案。
一个小坑点：题目中保证了对于每条边有 \(u_i<v_i\)，但是这并不代表 \(fa_i<i\)，这个条件其实没用。
代码很好写
#include "snowy.h"
using namespace std;
namespace anya{
const int M=505;
int n;
int cnt,ver[M<<1],nxt[M<<1],h[M],id[M<<1],fa[M],dep[M],dis[M],cntdep[17],dfn[M],minn;
int b[M];
inline void add_edge(int x,int y,int z){
cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;id[cnt]=z;
}
inline void dfs(int x){
cntdep[dep[x]%10]++;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa[x])continue;
fa[y]=x;
dep[y]=dep[x]+1;
dfs(y);
}
}
inline void dfs1(int x){
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa[x])continue;
dis[y]=dis[x]+b[id[i]];
dfs1(y);
}
}
}
void InitAnya(int N,int A[],int B[]){
using namespace anya;
n=N;
for(int i=0;i<n-1;i++){
add_edge(A[i]+1,B[i]+1,i);
add_edge(B[i]+1,A[i]+1,i);
}
dfs(1);
for(int i=1;i<10;i++)if(cntdep[i]<cntdep[minn])minn=i;
int cntdfn=0;
for(int i=2;i<=n;i++){
dfn[i]=cntdfn;
if(dep[i]%10==minn)cntdfn+=9;
else cntdfn++;
}
}
void Anya(int C[]){
using namespace anya;
for(int i=0;i<n-1;i++)b[i]=C[i];
dfs1(1);
for(int i=2;i<=n;i++){
if(dep[i]%10==minn){
for(int j=dfn[i]+8,x=dis[i];j>=dfn[i];j--)Save(j,x&1),x>>=1;
}
else Save(dfn[i],dis[i]-dis[fa[i]]);
}
}
namespace boris{
const int M=505;
int n;
int cnt,ver[M<<1],nxt[M<<1],h[M],fa[M],dep[M],dis[M],cntdep[17],dfn[M],minn;
inline void add_edge(int x,int y){
cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;
}
inline void dfs(int x){
cntdep[dep[x]%10]++;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa[x])continue;
fa[y]=x;
dep[y]=dep[x]+1;
dfs(y);
}
}
}
void InitBoris(int N,int A[],int B[]){
using namespace boris;
n=N;
for(int i=0;i<n-1;i++){
add_edge(A[i]+1,B[i]+1);
add_edge(B[i]+1,A[i]+1);
}
dfs(1);
for(int i=1;i<10;i++)if(cntdep[i]<cntdep[minn])minn=i;
int cntdfn=0;
for(int i=2;i<=n;i++){
dfn[i]=cntdfn;
if(dep[i]%10==minn)cntdfn+=9;
else cntdfn++;
}
}
int Boris(int city){
using namespace boris;
int x=city+1,ans=0;
while(dep[x]%10!=minn&&x!=1){
ans+=Ask(dfn[x]);
x=fa[x];
}
if(x!=1){
int s=0;
for(int i=dfn[x];i<dfn[x]+9;i++)s=(s<<1)|Ask(i);
ans+=s;
}
return ans;
}