7.10 冲刺国赛模拟 33
T1 染色
点分树模板。
另一做法是考虑差分，关键是求 \(\mathrm{LCA}\) 到跟距离的和，可以每次染色后使得到根的路径上 \(+1\)，这样查询时也查询到根的路径上权值和。
点击查看代码
int n,m;
struct edge{
int to,w,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
e[++cnt].to=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].w=w,e[cnt].nxt=head[v],head[v]=cnt;
}
namespace HLD{
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
ll dis[maxn];
int top[maxn];
void dfs1(int u,int d){
dep[u]=d,siz[u]=1;
int maxson=-1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(v==fa[u]) continue;
dis[v]=dis[u]+w;
dfs1(v,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];
}
}
void dfs2(int u,int t){
top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline void input(){
for(int v=2;v<=n;++v) fa[v]=read()+1;
for(int v=2;v<=n;++v){
int w=read();
add_edge(fa[v],v,w);
}
dfs1(1,0);
dfs2(1,1);
}
inline int get_LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
inline ll get_dis(int u,int v){
int lca=get_LCA(u,v);
return dis[u]+dis[v]-2*dis[lca];
}
}
namespace CDD{
int cd;
bool vis[maxn];
int siz[maxn],maxsiz[maxn],sumsiz;
int fa[maxn];
void dfs_siz(int u,int f){
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f||vis[v]) continue;
dfs_siz(v,u);
siz[u]+=siz[v];
}
}
inline void init(int u){
cd=0,sumsiz=siz[u];
}
void dfs_cd(int u,int f){
maxsiz[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f||vis[v]) continue;
dfs_cd(v,u);
maxsiz[u]=max(maxsiz[u],siz[v]);
}
maxsiz[u]=max(maxsiz[u],sumsiz-siz[u]);
if(!cd||maxsiz[u]<maxsiz[cd]) cd=u;
}
void build(int u){
vis[u]=1;
dfs_siz(u,0);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]) continue;
init(v);
dfs_cd(v,0);
fa[cd]=u;
build(cd);
}
}
int col[maxn];
int cntu[maxn],cntf[maxn];
ll sumu[maxn],sumf[maxn];
inline void update(int u){
for(int last=0,now=u;now;last=now,now=fa[now]){
ll d=HLD::get_dis(now,u);
++cntu[now],sumu[now]+=d;
if(last) ++cntf[last],sumf[last]+=d;
}
}
inline void query(int u){
ll res=0;
for(int last=0,now=u;now;last=now,now=fa[now]){
ll d=HLD::get_dis(now,u);
res+=d*cntu[now]+sumu[now];
if(last) res-=d*cntf[last]+sumf[last];
}
printf("%lld\n",res);
}
inline void solve(){
dfs_siz(1,0);
init(1);
dfs_cd(1,0);
build(cd);
while(m--){
int opt=read(),u=read()+1;
if(opt==1){
if(col[u]) continue;
col[u]=1;
update(u);
}
else query(u);
}
}
}
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
n=read(),m=read();
HLD::input();
CDD::solve();
return 0;
}
T2 寻宝游戏
题目暗示了做法。
考虑将判定的射线定义成由右下到左上且与水平方向夹角极小的射线，这样不会经过任何端点。
设 \(f_{i,j,S}\) 为到 \((i,j)\) 且每个宝藏或陷阱对应射线经过次数的奇偶状态为 \(S\) 的最小步数，转移类似 BFS，更改 \(S\) 时直接枚举每个宝藏或陷阱的位置。
点击查看代码
int n,m;
char s[25][25];
vector<pii> V;
int v[10];
int sx,sy,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int f[25][25][(1<<8)+10];
struct node{
int x,y,st;
node()=default;
node(int x_,int y_,int st_):x(x_),y(y_),st(st_){}
};
queue<node> q;
int ans;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
for(int j=1;j<=m;++j){
if(s[i][j]>='1'&&s[i][j]<='8'){
V.push_back(make_pair(i,j));
}
}
}
for(int i=1;i<=(int)V.size();++i) v[i]=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s[i][j]=='B') V.push_back(make_pair(i,j));
if(s[i][j]=='S') sx=i,sy=j;
}
}
memset(f,0x3f,sizeof(f));
f[sx][sy][0]=0;
q.push(node(sx,sy,0));
while(!q.empty()){
int x=q.front().x,y=q.front().y,st=q.front().st;
q.pop();
for(int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(s[xx][yy]!='.'&&s[xx][yy]!='S') continue;
int now=st;
for(int j=0;j<(int)V.size();++j){
if(x!=xx&&V[j].sec>y){
if(V[j].fir==max(x,xx)) now^=(1<<j);
}
}
if(f[x][y][st]+1<f[xx][yy][now]){
f[xx][yy][now]=f[x][y][st]+1;
q.push(node(xx,yy,now));
}
}
}
for(int i=0;i<(1<<(int)V.size());++i){
bool chk=1;
int sum=0;
for(int j=0;j<(int)V.size();++j){
if(!(i&(1<<j))) continue;
if(s[V[j].fir][V[j].sec]=='B') chk=0;
else sum+=v[s[V[j].fir][V[j].sec]-'0'];
}
if(chk){
ans=max(ans,sum-f[sx][sy][i]);
}
}
printf("%d\n",ans);
return 0;
}
T3 点分治
考虑树形 DP，重点是如何合并。
模拟将 \(u,v\) 两子树合并后的一个分治过程，在 \(u,v\) 都有节点被删去后，实际上产生影响的就是 \(u,v\) 所在连通块中删去的节点了（其他连通块合并前后不变）。如果只关心 \(u,v\) 所在连通块删去的过程，就是 \(u\) 子树和 \(v\) 子树分别考虑再按某种顺序拼起来。
设 \(f_{u,i}\) 为 \(u\) 子树的分治过程中，子树内节点（包括 \(u\)）在删去时与 \(u\) 连通的有 \(i\) 个的方案数。转移过程即枚举第二维后考虑 \(v\) 中有多少在 \(u\) 之前删去，可以后缀和优化。
点击查看代码
int n;
vector<int> E[maxn];
int C[maxn][maxn];
int siz[maxn];
int f[maxn][maxn],tmpf[maxn];
void dfs(int u,int fa){
siz[u]=1;
f[u][1]=1;
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u);
for(int i=1;i<=siz[u]+siz[v];++i) tmpf[i]=0;
for(int i=1;i<=siz[u];++i){
for(int j=0;j<=siz[v];++j){
tmpf[i+j]=(tmpf[i+j]+1ll*f[u][i]*f[v][j]%mod*C[i+j-1][i-1]%mod)%mod;
}
}
siz[u]+=siz[v];
for(int i=1;i<=siz[u];++i) f[u][i]=tmpf[i];
}
for(int i=siz[u];i>=0;--i) f[u][i]=(f[u][i+1]+f[u][i])%mod;
}
int main(){
freopen("dianfen.in","r",stdin);
freopen("dianfen.out","w",stdout);
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
C[0][0]=1;
for(int i=1;i<=n;++i){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
dfs(1,0);
printf("%d\n",f[1][0]);
return 0;
}