Atcoder abc302

https://atcoder.jp/contests/abc302/tasks

Ex

n点树,无向边,点上 有 写有数字Ai的球 和写有数字Bi的球

令 v = 2..n 个独立问题

• path(点1 到 v) 每个点 取一个球, 问 不同的数字 的个数 最大为多少

n 2e5

ai,bi [1,n]

2s

1024mb

我的思路

考虑把1选做根

那么每次查询的就是 当前点到根的路径上每次 选一个数， 选出数字 max(distinct)

显然 ans[u] - ans[fa[u]] \in [0,1]

---

如果单次求， 就是做并查集， 对于是树的 贡献 = 边

对于 不是树的（边 >= 点) 贡献是点

听起来 需要一个 可持久化 并查集?

点+点 = 树(+1)

点+树 = 树(+1)

点+图 = 图(+1)

树+树 = 树(+1)

树+图 = 图(+1)

图+图 = 图(+0)

树内部 = 图(+1)

图内部 = 图(+0)

题解

一样，先考虑对于给定v,那么就是

两个长度 len[1..v] 的序列A,B每次选Ai 或Bi 使得不同的值的个数尽量

然后就是N边图，Ai和Bi之间有边

ans = sum 所有连通块min(边,点)，

直接需要N^2时间，会TLE, 使用DSU优化

从1开始dfs

对于增加 ai-bi 和 删除ai-bi, 在dfs顺序上也就是 做dsu的你想操作

所以就是记录上一个状态的变化

并且采取小的向大的合并, 不做路径压缩

代码

https://atcoder.jp/contests/abc302/submissions/42714252

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
int const N=200000;
int a[N+10];
int b[N+10];
int f[N+10];
array<int,2> ev[N+10]; // edge vertex
int ans[N];
vector<int>e[N+10];
int find(int x){ return x==f[x]?x:find(f[x]); } // 不做路径压缩
void dfs(int x,int fa,int s){
  int fx=find(a[x]);
  int fy=find(b[x]);
  if(ev[fx][1] > ev[fy][1]) swap(fx,fy);
  auto [ex,vx] = ev[fx];
  auto [ey,vy] = ev[fy];
  if(fx != fy){
    f[fx] = fy;
    ev[fy] = {ex+ey+1,max(1,vx)+max(1,vy)};
    ans[x] = (s+= min(ev[fy][0],ev[fy][1]) - (min(ex,vx) + min(ey,vy)));
  }else{
    ev[fy] = {ey+1,max(1,vy)};
    ans[x] = (s+= min(ev[fy][0],ev[fy][1]) - min(ey,vy));
  }
  for(int y:e[x]) if(y!=fa) dfs(y,x,s);
  f[fx] = fx;
  ev[fy] = {ey,vy};
}
int main(){
  int n=read();
  rep(i,1,n+1){
    a[i]=read();
    b[i]=read();
    f[i]=i;
  }
  rep(i,1,n) {
    int x=read();
    int y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs(1,0,0);
  rep(i,2,n+1) printf("%d ",ans[i]);
  return 0;
}

总结

Ex

哎 2407的橙题卡住了

这个建图和连通块计数也想到了

所以核心就是 无路径压缩+启发式的可尾部撤销的DSU, 虽然大方向 想到了，但是这个第一次遇到，没想出来

参考

官方题解