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)\)。
CF1650G
与最短路距离不超过 \(1\)，而边权均为 \(1\)。所以这些路径不是最短路就是次短路。且是次短路的时候需要满足次短路长度只比最短路长 \(1\)。那么就是一个最短路和次短路的记数。直接跑即可。
CF489F
可以先把每一列的 \(1\) 数量限制记下来，记为 \(a_i\)。有 \(0\le a_i \le 2\)。对于每列进行考虑，定义状态函数 \(f_{i,j,k}\) 表示满足前 \(i\) 列的限制，在剩下的 \(n-m\) 行中有 \(j\) 行没有被填过 \(1\)，有 \(k\) 行被填了 \(1\) 个 \(1\)，剩下的 \(n-m-j-k\) 行被填完的方案数。那么只需要对 \(a_i\) 的值进行分类讨论转移了。转移是简单的。时间复杂度 \(O(n^3)\)。
CF659G
注意到我们切下来的是一个四联通块。那么记 \(p_i\) 表示第 \(i\) 列被切的位置，则对于相邻两列，如果都切了，一定有 \(p_i \le \min(a_i,a_{i+1})\land p_{i+1} \le \min (a_i,a_{i+1})\)。然后就做完了。如果我们第 \(i\) 列是结尾，则 \(p_i \le \min(a_i,a_{i-1})\)，记 \(f_i\) 为从前 \(i\) 列的某一列开始切，且第 \(i+1\) 列要切的方案数。如果我们 \(i\) 切完就不切了，有：\(ans_i=\min(a_i,a_{i-1})\times f_{i-1}+a_i\)。如果我们不结束，还需要满足 \(p_i \le \min(a_i,a_{i+1})\)，那么有：\(f_i =\min(a_i,a_{i+1})+\min(a_i,a_{i-1},a_{i+1}) \times f_{i-1}\)。时间复杂度 \(O(n)\)。因为我们不能切完，所以这里钦定 \(a_i\) 为原 \(a_i-1\)。
CF1418G
唐诗。
有个典 trick，判定一段区间内每个数是否出现偶数次可以直接全部异或起来。只要是 \(0\)，大概率说明一个值 \(x\) 出现了偶数次。然后对每个值重新给个随机值错误率就极小。
那么这题可以直接仿照这个思路。考虑分治。我们对 \(x\) 出现 \(y\) 次给一个随机值。那么只需要满足分治中心左边每个数 \(x\) 出现 \(cnt_x\) 次的值与右边每个数 \(x\) 出现 \(3-cnt_x’\) 的值异或起来为 \(0\) 就大概率对。而因为一个数不能出现大于 \(3\) 次，所以我们对于每个枚举的起点应该有一个右端点的限制。则只需要维护区间内某个数的出现次数就能解决了。时间复杂度 \(O(n\log^2 n)\)。
CF1744F
考虑什么样的区间满足条件。区间内的中位数 \(x\) 一定有性质：区间内不大于 \(x\) 的数不小于区间长度的一半。那么对于一个满足条件的区间，因为 \(0\sim mex-1\) 全部出现过，所以 \(2 \times mex \ge len\) 时这个区间就是满足条件的区间。考虑枚举 \(mex\)，我们能够得到一个最小的区间 \([l,r]\)，使得这个区间的 \(mex=x\)。记 \(p_i\) 为 \(a_j=i\) 的下标。那么当 \(p_{x} < l\) 时，只要我们 $p_{x} <l’ \le l \land r \le r’ \le n \land 2\times x\ge r’-l’+1 $ 就是一个合法的区间。\(p_{x}>r\) 同理。那么我们只需要枚举 \(l’\) 或 \(r’\) 就能得到所有合法区间的数量了。这里有个 trick，我们只需要每次枚举限制长度小的一边，就貌似是 \(O(n\log n)\) 的。具体我不会，但是跑得很快。
CF1702G1/G2
先不考虑 \(k\) 个节点的限制。考虑一棵树是否合法。既然我们每条边不能重复经过，那么最有策略显然是从一个叶子节点出发，走到另一个叶子节点。而对于一个中间节点，如果它的度数不小于 \(3\)，那么我们只能从它的其中一边走到它，在走到另外两边的一边，再回来走另一边。不难发现这显然会经过同样的边。那么这棵树合法当且仅当这棵树是条链。
注意到 \(\sum k \le 2\times 10^5\)。由于其它节点实际上是没有用的，我们直接建立虚树。那么只要这棵虚树是条链就合法了。时间复杂度 \(O(\sum k \log \sum k)\)。
来源链接：https://www.cnblogs.com/harmisyz/p/18656697
如有侵犯您的版权，请及时联系3500663466#qq.com(#换@)，我们将第一时间删除本站数据。
暂无评论内容