2025.1.7 做题记录
CF600E
dsu on tree 裸题。
P3899
考虑对 \(a,b\) 的关系分类讨论。对于 \(\operatorname{LCA}(a,b)=b\) 的情况,那么 \(a,b\) 的公共后代一定在 \(a\) 的子树内。即对于所有的 \((a,b)\),其贡献为 \(siz_a-1\)。因为 \(dep_b +k \ge dep_a\),所以 \(dep_b \ge dep_a-k\),每个 \(b\) 的贡献为 \(siz_a-1\)。对于 \(\operatorname{LCA}(a,b)=a\) 的情况,那么 \(a,b\) 的公共后代一定在 \(b\) 子树内。即对于所有 \((a,b)\),其贡献为 \(siz_b-1\)。因为 \(dep_b-k \le dep_a\),所以 \(dep_b \le dep_a+k\),每个 \(b\) 的贡献为 \(siz_b-1\)。
那么问题就变成了,求 \(\sum\limits_{\operatorname{LCA}(a,b)=b\land dep_b \ge dep_a-k}^{} siz_a-1 + \sum\limits_{\operatorname{LCA}(a,b)=a\land dep_b \le dep_a+k}^{}siz_b-1\)。前者可以直接计算,因为 \(a\) 已知。后者拍到 DFS 序上就是区间内 \(dep\) 不超过 \(dep_a+k\) 的 \(siz-1\) 的和。可以直接主席树维护。时间复杂度 \(O(n\log n)\)。
P3703
染上一个没有染过的点比较麻烦。不如直接染成 \(x\),因为点的编号不同,不肯能有两个 \(x,y (x\ne y)\) 进行操作 \(1\) 得到了相同的值,且仅可能有 \(x\) 到根的路径上存在这个颜色。那么对于求 \(x\) 到 \(y\) 的路径价值,我们就可以树剖维护。对于线段树维护其左端点的颜色,右端点的颜色,这个区间的价值。合并的时候只要相邻的颜色有重复,说明颜色段需要 \(-1\)。对于查询 \(x\) 子树内点到根价值最大值,因为我们相同的颜色肯定是一个点到根路径的前缀。那么当我们进行赋值操作的时候,可以维护出每个颜色的起始位置与终点位置。当我们将 \(1\) 到 \(x\) 的路径覆盖时,一个完全被覆盖的颜色 \(c\) 就会对其子树的颜色产生 \(-1\) 的贡献。由于每个颜色最多被删除和添加共 \(O(n)\) 次,所以暴力维护即可。
我们将两个问题分开考虑。第一个使用树剖维护颜色段,第二个使用普通线段树维护区间最大值。时间复杂度 \(O(n\log^2 n)\)。
代码
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N=2e5+10;
int n,m;
int val[N];
vector<int> e[N];
int mson[N],siz[N],top[N];
int id[N],dfn[N],cnt,dep[N],f[N];
int jump[N][22];
struct Tree1{
int l,r;
int cl,cr;
int val,tag;
}tr[N<<2];
struct Tree2{
int l,r;
int tag,mx;
}tr_[N<<2];
int Top[N],Bot[N];
il void up_(int u){
tr_[u].mx=max(tr_[ls(u)].mx,tr_[rs(u)].mx);
return ;
}
il void down_(int u){
if(!tr_[u].tag) return ;
tr_[ls(u)].tag+=tr_[u].tag,
tr_[rs(u)].tag+=tr_[u].tag;
tr_[ls(u)].mx+=tr_[u].tag,
tr_[rs(u)].mx+=tr_[u].tag;
return tr_[u].tag=0,void(0);
}
il void build_(int u,int l,int r){
tr_[u].l=l,tr_[u].r=r;
if(l==r) return tr_[u].mx=dep[id[l]],void(0);
int mid=l+r>>1;
build_(ls(u),l,mid),build_(rs(u),mid+1,r);
return up_(u),void(0);
}
il void modify_(int u,int l,int r,int x){
if(tr_[u].l>=l&&tr_[u].r<=r){
tr_[u].mx+=x,tr_[u].tag+=x;
return ;
}
down_(u);
int mid=tr_[u].l+tr_[u].r>>1;
if(l<=mid) modify_(ls(u),l,r,x);
if(mid< r) modify_(rs(u),l,r,x);
return up_(u),void(0);
}
il int query_(int u,int l,int r){
if(tr_[u].l>=l&&tr_[u].r<=r) return tr_[u].mx;
down_(u);
int mid=tr_[u].l+tr_[u].r>>1,mx=0;
if(l<=mid) mx=max(mx,query_(ls(u),l,r));
if(mid< r) mx=max(mx,query_(rs(u),l,r));
return mx;
}
il void up(Tree1 &u,Tree1 x,Tree1 y){
u.val=x.val+y.val-(x.cr==y.cl);
u.cl=x.cl,u.cr=y.cr;
return ;
}
il void down(int u){
if(!tr[u].tag) return ;
tr[ls(u)].tag=tr[rs(u)].tag=tr[u].tag;
tr[ls(u)].cl=tr[ls(u)].cr=tr[u].tag;
tr[rs(u)].cl=tr[rs(u)].cr=tr[u].tag;
tr[ls(u)].val=tr[rs(u)].val=1;
return tr[u].tag=0,void(0);
}
il void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
if(l==r) return tr[u].cl=tr[u].cr=id[l],tr[u].val=1,void(0);
int mid=l+r>>1;
build(ls(u),l,mid),build(rs(u),mid+1,r);
return up(tr[u],tr[ls(u)],tr[rs(u)]),void(0);
}
il void modify(int u,int l,int r,int x){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].val=1,tr[u].tag=x;
tr[u].cl=tr[u].cr=x;
return ;
}
down(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(ls(u),l,r,x);
if(mid< r) modify(rs(u),l,r,x);
return up(tr[u],tr[ls(u)],tr[rs(u)]),void(0);
}
il Tree1 query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
down(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid&&mid< r){
Tree1 V;
memset(&V,0,sizeof(V));
up(V,query(ls(u),l,r),query(rs(u),l,r));
return V;
}
if(l<=mid) return query(ls(u),l,r);
if(mid< r) return query(rs(u),l,r);
debug();
}
il int Query_(int u,int x){
if(tr[u].l==tr[u].r) return tr[u].cl;
down(u);
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid) return Query_(ls(u),x);
if(mid< x) return Query_(rs(u),x);
}
il void dfs1(int u,int fa){
int msiz=0;
jump[u][0]=fa;
for(re int i=1;i<22;++i) jump[u][i]=jump[jump[u][i-1]][i-1];
f[u]=fa,dep[u]=dep[fa]+1,mson[u]=-1,siz[u]=1;
for(auto v:e[u])
if(v!=fa){
dfs1(v,u),siz[u]+=siz[v];
if(msiz<siz[v]) msiz=siz[v],mson[u]=v;
}
return ;
}
il void dfs2(int u,int Tp){
id[++cnt]=u,dfn[u]=cnt;
top[u]=Tp;
if(~mson[u]) dfs2(mson[u],Tp);
for(auto v:e[u])
if(v!=f[u]&&v!=mson[u]){
dfs2(v,v);
}
return ;
}
il int Up(int u,int S){
int p=0;
while(S){
if(S&1) u=jump[u][p];
S>>=1,++p;
}
return u;
}
il void Modify(int x,int y,int z){
int lst=0;int To=0;
int X=x,Y=y,Z=z;Bot[z]=x,Top[z]=1;
while(x){
int Col=Query_(1,dfn[x]);
int Val=query_(1,dfn[x],dfn[x]);
int id1=top[x],id2=Top[Col];
if(dep[id1]<dep[id2]){
modify(1,dfn[id2],dfn[x],z);
modify_(1,dfn[id2],dfn[id2]+siz[id2]-1,-(Val-1));
if(lst) modify_(1,dfn[lst],dfn[lst]+siz[lst]-1,(Val-1));
}
else{
modify(1,dfn[id1],dfn[x],z);
modify_(1,dfn[id1],dfn[id1]+siz[id1]-1,-(Val-1));
if(lst) modify_(1,dfn[lst],dfn[lst]+siz[lst]-1,(Val-1));
}
if(x!=Bot[Col]){
int x_=Up(Bot[Col],dep[Bot[Col]]-dep[x]-1);
if(x_!=lst) modify_(1,dfn[x_],dfn[x_]+siz[x_]-1,1),To=x_;
}
if(dep[id2]<dep[id1]) x=f[id1],lst=id1;
else x=f[id2],lst=id2,Top[Col]=To;
}
return ;
}
il int Query(int x,int y){
Tree1 ans1,ans2;
memset(&ans1,0,sizeof(ans1));
memset(&ans2,0,sizeof(ans2));
while(top[x]!=top[y]){
if(dep[top[x]]>=dep[top[y]]){
Tree1 ans=query(1,dfn[top[x]],dfn[x]);
x=f[top[x]];
up(ans1,ans,ans1);
}
else{
Tree1 ans=query(1,dfn[top[y]],dfn[y]);
y=f[top[y]];
up(ans2,ans,ans2);
}
}
if(dep[x]>=dep[y]) up(ans1,query(1,dfn[y],dfn[x]),ans1);
if(dep[x]< dep[y]) up(ans2,query(1,dfn[x],dfn[y]),ans2);
swap(ans1.cl,ans1.cr);
up(ans2,ans1,ans2);
return ans2.val;
}
il void solve(){
n=rd,m=rd;
for(re int i=1;i< n;++i){
int u=rd,v=rd;
e[u].push_back(v),
e[v].push_back(u);
}
dfs1(1,0),top[1]=1,dfs2(1,1);
build(1,1,n),build_(1,1,n);
for(re int i=1;i<=n;++i) Top[i]=Bot[i]=i;int Cnt=n;
while(m--){
int op=rd;
if(op==1){
int x=rd;
Modify(x,1,++Cnt);
}
else if(op==2){
int x=rd,y=rd;
printf("%lld\n",Query(x,y));
}
else if(op==3){
int x=rd;
printf("%lld\n",query_(1,dfn[x],dfn[x]+siz[x]-1));
}
}
return ;
}
CF1280C
考虑对于一条连接 \(u,v\) 的边。如果我们要让路径和最小,显然是不愿意将一对人分在 \(u,v\) 两侧的。那么记 \(siz_u\) 表示 \(u\) 为根的子树大小。\(f_u\) 表示最小代价和。那么有 \(f_u=\sum\limits_{v\in son_u}^{}f_v+w_{u,v}[siz_v ~is ~odd]\)。那么最大价值和同理,我们要让它们尽量经过这条边,有 \(g_u=\sum\limits_{v\in son_u}^{}f_v+w_{u,v}\times \min(n-siz_v,siz_v)\)。时间复杂度 \(O(n)\)。
CF1304E
先考虑如果没有加边时的情况。那么很显然的,只要 \(dis_{a,b} \le k\) 且 \(k-dis_{a,b}\) 为偶数就可以了。因为题目不要求走简单路径,而我们折返一次一条边需要经过 \(2\) 次。那么加上 \(x,y\) 这条边同理,我们只需要再计算经过 \(x,y\) 这条边是否可行即可。即 \(dis_{a,x}+1+dis_{y,b} \le k\) 且 \(k-(dis_{a,x}+1+dis_{y,b} )\) 为偶数或 \(dis_{a,y}+1+dis_{x,b} \le k\) 且 \(k-(dis_{a,y}+1+dis_{x,b} )\) 为偶数。时间复杂度 \(O(n\log n)\)。