重修 线段树分治
Emm 不知道讲啥算了直接放例题。
CF1681F Unique Occurrences
给定一个 \(n\) 个结点的树，每条边有一个颜色，记 \(f(x,y)\) 表示结点 \(x\) 到 \(y\) 的路径上只出现了一次的颜色的数量，求 \(\sum\limits_{x < y}f(x, y)\)。数据保证 \(n \le 5 \times 10^5\)。
如果现在考虑颜色 \(w\)，那么删去所有该颜色的边，求得剩下每个连通块的大小，那么每条颜色 \(w\) 的边的贡献就是两端连通块大小的乘积。这个过程可以通过线段树分治+带撤销并查集快速维护。
\(O(n\log^2 n)\)
具体地，我们将每一种颜色看作数组中的下标，构建线段树。
若有一条 \((x,y)\) 颜色为 \(z\) 的边，那线段树 \([1,z-1]\) 及 \([z+1,n]\) 区间 push_back 这条 \((x,y)\) 边，表示在算这些颜色的贡献的时候这条边会被算进并参与并查集。
然后就线段树直接 DFS，一路下来维护并查集，然后到叶子的时候统计贡献，回去的时候记得撤销。
点击查看代码
#include
using namespace std;
#define int long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pi pair
#define N 500010
#define pb emplace_back
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define fir first
#define sec second
#define mkp make_pair
int n,ans=0,f[N],sz[N];
vector e[N],g[N<<2];
inline int gf(int x){return x==f[x]?x:gf(f[x]);}//no path-zip
void add(int rt,int l,int r,int x,int y,pi z){
if(l==x && r==y){
g[rt].pb(z);
return ;
}
if(y<=mid) add(ls,l,mid,x,y,z);
else if(x>mid) add(rs,mid+1,r,x,y,z);
else add(ls,l,mid,x,mid,z),add(rs,mid+1,r,mid+1,y,z);
}
int del[N],tot=0;
inline void merge(int x,int y){
x=gf(x);y=gf(y);
if(sz[x]re) antimerge();
}
signed main(){IOS;
cin>>n;
For(i,1,n) f[i]=i;
For(i,1,n) sz[i]=1;
int x,y,z;
For(i,1,n-1){
cin>>x>>y>>z;
e[z].pb(mkp(x,y));
if(z>1) add(1,1,n,1,z-1,mkp(x,y));
if(z CF1680F Lenient Vertex Cover
求一个 \(n\) 个点、\(m\) 条边的无向连通图是否能够删掉仅一条边后成为二分图（或者本身就是）。
这里官方是 \(O(n)\) 做法，但是 \(O(n\log^2 n)\) 也能卡过对吧。
我的题解
CF1442D Sum
给定 \(n\) 个不降的数组。有一个值 \(ans\)，初始为 \(0\)。你需要进行如下操作 \(k\) 次：
选择一个数组，把 \(ans\) 加上数组的第一个元素，之后把它删除。
请求出 \(ans\) 的最大值。
所有数组的元素总个数 \(\leq 10^6,n,k\leq 3000\)
先要有一个结论：最多有一个数组没有被取完。（大佬们可能能手玩出来）
当然证明和理解都不难，略。
我们考虑分治这个没有取完的是哪个数组。
除了这个数组，其它都可以看作单件物品，和 \(01\) 背包相同。
最后再和这个特殊的数组合并一下即可。
时间复杂度 \(O(nk\log n)\)
点击查看代码
#include
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define pi pair
#define N 3030
#define mkp make_pair
#define fir first
#define sec second
#define pb emplace_back
#define vi vector
#define ckmx(a,b) a=max(a,b)
vi v[N],f;
int sum[N],sz[N],ans=0,n,k;
void work(int l,int r){
if(l==r){
int x=0,y=0;
for(int i:v[l]){
y++;x+=i;
if(y>k) break;
ckmx(ans,f[k-y]+x);
}
return ;
}
int mid=(l+r)>>1;
vi re=f;
For(i,mid+1,r)
Rof(j,k,sz[i])
ckmx(f[j],f[j-sz[i]]+sum[i]);
work(l,mid);
f=re;
For(i,l,mid)
Rof(j,k,sz[i])
ckmx(f[j],f[j-sz[i]]+sum[i]);
work(mid+1,r);
}
signed main(){IOS;
cin>>n>>k;
For(i,0,k) f.pb(0);
int x,y;
For(i,1,n){
cin>>x;
sz[i]=x;
while(x--){
cin>>y;
v[i].pb(y);
sum[i]+=y;
}
}
work(1,n);
cout<