省選模擬6
A. 中心城鎮問題
設 \(f_{i,j}\) 表示以 \(i\) 為根的子樹內里 \(i\) 最近的選擇點的深度為 \(j\)
轉移的話
\((j-dep_x)*2>K\) 直接加上對應的位置
\(0 < (j-dep_x)*2\leq K\) 需要判斷保證選擇的子樹之間的距離要大於 \(K\)
還有一種 \(f_i,dep_i=f_i,dep_{i+k+1}+w_i\) 選擇自己的情況
是以下標為深度的轉移，於是長鏈剖分優化一下就行
還有保證是後綴最大值
Code
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,k;
int w[1000010],son[1000010],dep[1000010],md[1000010];
int head[1000010],ver[2000010],to[2000010],tot;
vector<int>f[1000010],vec;
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
void dfs1(int x,int fa){
md[x]=dep[x]=dep[fa]+1;
for(int i=head[x];i;i=to[i]){
int y=ver[i];
if(y==fa) continue;
dfs1(y,x);
md[x]=max(md[x],md[y]);
if(md[y]==md[x]) son[x]=y;
}
}
void dfs2(int x,int fa){
if(!son[x]) return f[x].emplace_back(w[x]),void();
dfs2(son[x],x);swap(f[x],f[son[x]]);
if(f[x].size()>k){
f[x].emplace_back(max(f[x][f[x].size()-1-k]+w[x],f[x].back()));
}else f[x].emplace_back(max(w[x],f[x].size()?f[x].back():0ll));
for(int i=head[x],s,t,e;i;i=to[i]){
int y=ver[i];
if(y==fa||y==son[x]) continue;
dfs2(y,x);e=f[y].size()-1;
t=f[x].size()-1;s=t-f[y].size();
for(int i=s;i<=t;i++) vec[i]=0;
for(int i=s,d;i<=t;i++){
d=dep[x]+t-i;vec[i]=f[x][i];
if(2*(d-dep[x])>k){
vec[i]+=f[y][f[y].size()-1-(d-dep[y])];
}else if(2*(d-dep[x])>0){
if(e-(k+1-d+2*dep[x]-dep[y])>=0) vec[i]=max(vec[i],f[x][i]+f[y][e-(k+1-d+2*dep[x]-dep[y])]);
if(t-(k+1-d+2*dep[x]-dep[x])>=0&&d!=(k+1-d+2*dep[x])) vec[i]=max(vec[i],f[x][t-(k+1-d+2*dep[x]-dep[x])]+f[y][e-(d-dep[y])]);
}else if(md[y]>dep[x]+k){
vec[i]=max(vec[i],f[x][t]+f[y][e-(dep[x]+1+k-dep[y])]);
}
if(i>s) vec[i]=max(vec[i],vec[i-1]);
if(d-dep[y]>=0) vec[i]=max(vec[i],f[y][e-(d-dep[y])]);
}
for(int i=s;i<=t;i++) f[x][i]=vec[i];
f[y].clear();f[y].shrink_to_fit();
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("central.in","r",stdin);
freopen("central.out","w",stdout);
n=read(),k=read();vec.resize(1000010);
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1,x,y;i<n;i++){
x=read(),y=read();
add(x,y),add(y,x);
}
dfs1(1,0);dfs2(1,0);
printf("%lld\n",f[1].back());
return 0;
}
B. 心理陰影
一個點對產生貢獻時，只跟分別到 \(lca\) 處的路徑上的點有關，跟其他點無關
於是考慮在 \(lca\) 處合併子樹之間的答案
設 \(siz_u\) 表示 \(u\) 的子樹大小， \(g(u,v)\) 表示 \(v\) 子樹內比 \(u\) 小的數的個數
\(f_{u,v}\) 表示將 \(u,v\) 子樹合併時產生的逆序對的平均數
分別是先選 \(u\) 的情況和先選 \(v\) 的情況
先選了 \(u\) 那麼要加上 \(u\) 的每一個子樹和 \(v\) 去合併的貢獻，還有 \(g(u,v)\)
由於每個子樹之間互補影響與 \(v\) 的貢獻，所以可以直接加
先選 \(v\) 的同理
還需要乘上一個係數
最後就是 \(f(u,v)=\frac{siz_u*(\sum\limits_{w}f(w,v)+g(u,v))+siz_v*(\sum\limits_w f(w,u)+g(v,u))}{siz_u+siz_v}\)
還有一種情況，就是為祖先關係時，無論如何都會產生貢獻要單獨加上
Code
#include<bits/stdc++.h>
//#define int long long
#define rint signed
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,rt,ans;
int inv[5000],siz[5000],fa[5000];
int head[5000],ver[10000],to[10000],tot;
int f[5000][5000],g[5000][5000];
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
inline void md(int &x){x=(x>=mod)?x-mod:x;}
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=1ll*res*base%mod;base=1ll*base*base%mod;k>>=1;}
return res;
}
void dfs(int x,int fath){
fa[x]=fath;siz[x]=1;for(int i=x+1;i<=n;i++) g[i][x]++;
for(int i=head[x];i;i=to[i]){
int y=ver[i];if(y==fath) continue;
dfs(y,x);siz[x]+=siz[y];
for(int i=1;i<=n;i++) g[i][x]+=g[i][y];
}
}
inline int calc(int x,int y){
if(~f[x][y]) return f[x][y];
md(f[x][y]=(1ll*siz[x]*g[x][y]%mod+1ll*siz[y]*g[y][x]%mod));
for(int i=head[x];i;i=to[i]){
int z=ver[i];if(z==fa[x]) continue;
md(f[x][y]+=1ll*siz[x]*calc(z,y)%mod);
}
for(int i=head[y];i;i=to[i]){
int z=ver[i];if(z==fa[y]) continue;
md(f[x][y]+=1ll*siz[y]*calc(z,x)%mod);
}
f[x][y]=1ll*f[x][y]*inv[siz[x]+siz[y]]%mod;
return f[y][x]=f[x][y];
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("nightmare.in","r",stdin);
freopen("nightmare.out","w",stdout);
for(int i=1;i<=4096;i++) inv[i]=qpow(i,mod-2);
n=read(),rt=read();
for(int i=1,x,y;i<n;i++){x=read(),y=read();add(x,y),add(y,x);}
dfs(rt,0);memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) ans+=g[i][i];
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=to[j]){
int x=ver[j];if(x==fa[i]) continue;
for(int k=head[i];k;k=to[k]){
int y=ver[k];if(y==fa[i]) continue;if(x>=y) continue;
md(ans=(ans+calc(x,y)));
}
}
}
printf("%d\n",ans);
return 0;
}
C. Pajel 遊戲
手模前 \(4\) 個，第 \(5\) 個並查集縮一下再染色就行
後面的右手扶牆走，碰到一個不一樣的顏色就換一種顏色染，最後再手動調整
