[关闭]
@2368860385 2020-11-07T03:00:51.000000Z 字数 4722 阅读 176

前：day3考试

衢州

考试总结

T1

没见过这种hash。。。
于是暴力，后面链的情况写了，过了自己造的样例，然后先交了一下。之后写对拍，然后发现链的情况有问题，然后改，然后就忘记在交一遍了。。

T2

5分感觉好少，于是想30分的做法。。。
于是想到是先是一棵树，只有几十个双联通分量。对于非双联通分量里的点都是-1，叶子节点特判一下，强联通分量里的点需要处理一下。

处理好麻烦！！！！！

为什么这样想好像对，写不对？细节太多，复杂度还不大正确，出题人不是这样想的。

T3

5分，直接枚举，还有地方没处理好。

题解

T1

对一棵子树求出 hash ，放到set里，然后在另一棵树里查询。
可以开n个set，表示大小为n的子树。

当前子树的大小为k，那么对于另一棵子树中，所有对应的点，的lca，以这个lca为根的子树中，大小为看k。
可以放到dfs序上处理。

集合hash，只查询元素有没有，不需要查询顺序。

zobrist hashing

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<vector>
  8. #include<set>
  9. using namespace std;
  10. typedef long long LL;
  12. inline int read() {
  13.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  14.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  15. }
  17. const int N = 200010;
  19. vector<int>T[N];
  20. LL key[N], Hash[N];
  21. int siz[N], Ans;
  22. set<LL>s[N];
  24. void init(int x) {
  25.     LL a = (rand() << 15) | rand();
  26.     LL b = (rand() << 15) | rand();
  27.     key[x] = a * b;
  28. }
  30. void dfs1(int u,int pa) {
  31.     siz[u] = 1, Hash[u] = key[u];
  32.     int sz = T[u].size();
  33.     for (int i=0; i<sz; ++i) {
  34.         int v = T[u][i];
  35.         if (v == pa) continue;
  36.         dfs1(v,u);
  37.         siz[u] += siz[v];
  38.         Hash[u] ^= Hash[v]; 
  39.     }
  40.     if (u == 1) return ;
  41.     s[siz[u]].insert(Hash[u]);
  42. }
  43. void dfs2(int u,int pa) {
  44.     siz[u] = 1, Hash[u] = key[u];
  45.     int sz = T[u].size();
  46.     for (int i=0; i<sz; ++i) {
  47.         int v = T[u][i];
  48.         if (v == pa) continue;
  49.         dfs2(v,u);
  50.         siz[u] += siz[v];
  51.         Hash[u] ^= Hash[v]; 
  52.     }
  53.     if (u == 1) return ;
  54.     if (s[siz[u]].count(Hash[u])) Ans ++;
  55. }
  57. int main() {
  58.     int n = read();
  59.     for (int i=1; i<=n; ++i) init(i);
  60.     for (int i=1; i<n; ++i) {
  61.         int u = read(),v = read();
  62.         T[u].push_back(v);
  63.         T[v].push_back(u);
  64.     }
  65.     dfs1(1,0);
  66.     for (int i=1; i<=n; ++i) T[i].clear();
  67.         for (int i=1; i<n; ++i) {
  68.         int u = read(),v = read();
  69.         T[u].push_back(v);
  70.         T[v].push_back(u);
  71.     }
  72.     dfs2(1,0);
  73.     cout << Ans;
  74.     return 0;
  75. }

T2

题意：对于每个点i，求出从这个点出发，选一条边，然后遍历完所有点（中途不能回到i，每条边可以走多次），再从选的边回到这个点的经过的最大的边最小是多少。

m=n+60，求出MST，枚举每个点被删除后，然后再枚举剩余60条边，加入。

先求一遍MST，然后从小到大，枚举非树边。

考虑返祖边：u->v，边权为w，这条边，那么所有fa[u]->son[v]的点（就是这条路径经过的点中，不包含uv的点），会对更新这些点（称为更新点，假设i是这些点中的一个，因为去掉这个点i后，形成了degree[i]个联通块，需要把这些联通块在连起来，而这条边就会使 i的fa所在的联通块 和 u所在的联通块合起来）。

如何更新贡献：对于一个 路径点（路径u->v上的点）i，其父节点p（要求p一定是更新点，所以不能是v），由于去掉p后，它的子节点i，可以连向p的fa所在的联通块，所以更新ans[p]=w。因为i对p产生了贡献，所以称i为贡献点。以此类推，就可以更新完所有的更新点。
i做为贡献点，更新了p，之后i不会再成为贡献点去更新p了。因为去掉p后形成的联通块中，i所在的联通块，用u->v这条边连接是最优的，所以就用u->v连接了。所以如果再有路径可以让i对p产生贡献，可以直接跳到p。而p也许已经做过贡献点了，又跳到了p的fa……所以用并查集维护，将做过贡献点的指向最近的一个没做过贡献点。

合并：u就是贡献点，v是更新点（u相当于i，v相当于p）。

  1. void Merge(int u,int v) {
  2.     u = find(u), v = find(v);
  3.     if (u != v) fa[u] = v; // 顺序不能反
  4. }

横插边：u->v，可以拆成u->lca,v->lca两条返租边来做，lca也是更新点，而拆成的两路径不能更新lca，所以最后判断一下。

核心代码，路径u->v，权值w，u是贡献点，p是更新点。

  1. while (deth[p] > deth[v]) {
  2.    ans[p] = w; dgr2[p]++; Merge(u, p);            
  3.    u = find(u), p = f[u][0];
  4. }

统计答案：如果一个点更新了degree[i]-1次，那么说明将i去掉后，可以形成联通块，答案是ans[i]，否则答案是-1。特判一下叶子节点。

每个点最多做一次贡献点，如果lca使用求的话，复杂度是

tips：撤销操作，用一个栈记录操作序列。
tipS树套树：log，维护外面树对套树的映射。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<cctype>
  6. #include<vector>
  7. using namespace std;
  8. typedef long long LL;
  10. inline int read() {
  11.     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
  12.     for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
  13. }
  15. const int N = 1000100;
  17. struct Edge{
  18.     int u, v, w;
  19.     Edge() {}
  20.     Edge(int a,int b,int c) {u = a, v = b, w = c;}
  21.     bool operator < (const Edge &A) const {
  22.         return w < A.w; 
  23.     }
  24. }e[N];
  25. int Enum, tot;
  26. int g[N], fa[N], f[N][21], dgr1[N], dgr2[N], deth[N], ans[N];
  27. vector<int>T[N];
  29. int find(int x) {
  30.     return x == fa[x] ? x : fa[x] = find(fa[x]);
  31. }
  32. int Kruskal(int n,int m) {
  33.     for (int i=1; i<=n; ++i) fa[i] = i;
  34.     int cnt = 0, ans = -1;
  35.     sort(e + 1, e + m + 1);
  36.     for (int i=1; i<=m; ++i) {
  37.         int u = e[i].u, v = e[i].v;
  38.         int fu = find(u), fv = find(v);
  39.         if (fu == fv) {
  40.             g[++tot] = i; continue;
  41.         }
  42.         ++cnt; fa[fu] = fv; ans = e[i].w; 
  43.         dgr1[u] ++; dgr1[v] ++;
  44.         T[u].push_back(v); T[v].push_back(u);
  45.     }
  46.     if (cnt == n - 1) return ans;
  47.     return -1;
  48. }
  50. void dfs(int u,int fa) {
  51.     deth[u] = deth[fa] + 1;
  52.     for (int sz=T[u].size(), i=0; i<sz; ++i) {
  53.         int v = T[u][i];
  54.         if (v == fa) continue;
  55.         f[v][0] = u;
  56.         dfs(v, u);
  57.     }
  58. }
  59. int Lca(int u,int v) {
  60.     if (deth[u] < deth[v]) swap(u, v);
  61.     int d = deth[u] - deth[v];
  62.     for (int i=20; i>=0; --i) 
  63.         if (d & (1 << i)) u = f[u][i];
  64.     if (u == v) return u;
  65.     for (int i=20; i>=0; --i) 
  66.         if (f[u][i] != f[v][i]) 
  67.             u = f[u][i], v = f[v][i];
  68.     return f[u][0];
  69. }
  71. void Merge(int u,int v) {
  72.     u = find(u), v = find(v);
  73.     if (u != v) fa[u] = v;
  74. }
  75. int main() {
  76.     int n = read(), m = read();
  77.     for (int i=1; i<=m; ++i) {
  78.         int u = read(), v = read(), w = read();
  79.         e[++Enum] = Edge(u, v, w);
  80.     }
  81.     int Minans = Kruskal(n, m);
  82.     if (Minans == -1) {
  83.         cout << -n; return 0;
  84.     }
  86.     dfs(1, 0);
  87.     for (int j=1; j<=20; ++j) 
  88.         for (int i=1; i<=n; ++i) 
  89.             f[i][j] = f[f[i][j-1]][j-1];
  91.     for (int i=1; i<=n; ++i) fa[i] = i;
  93.     for (int i=1; i<=tot; ++i) {
  94.         int u = e[g[i]].u, v = e[g[i]].v, w = e[g[i]].w, p, tu, tv;
  95.         if (deth[u] < deth[v]) swap(u, v);
  96.         int x = Lca(u, v);
  97.         if (x == v) {
  98.             u = find(u), p = f[u][0];
  99.             while (deth[p] > deth[v]) {
  100.                 ans[p] = w; dgr2[p]++; Merge(u, p);
  101.                 u = find(u), p = f[u][0];
  102.             }
  103.         }
  104.         else {
  105.             tu = u, tv = v;
  106.             u = find(u), p = f[u][0];
  107.             while (deth[p] > deth[x]) {
  108.                 ans[p] = w; dgr2[p]++; Merge(u, p);
  109.                 u = find(u), p = f[u][0];
  110.             }
  111.             v = find(v), p = f[v][0];
  112.             while (deth[p] > deth[x]) {
  113.                 ans[p] = w; dgr2[p]++; Merge(v, p);
  114.                 v = find(v), p = f[v][0];
  115.             }
  116.             u = find(tu), v = find(tv);
  117.             if (u != v) {
  118.                 if (deth[u] < deth[v]) swap(u, v);
  119.                 ans[x] = w; dgr2[x]++; Merge(u, v);
  120.             }
  121.         }
  122.     }
  124.     LL Ans = 0;
  125.     for (int i=1; i<=n; ++i) {
  126.         if (dgr1[i] == 1) Ans += Minans;
  127.         else if (dgr2[i] < dgr1[i] - 1) Ans --;
  128.         else Ans += max(Minans, ans[i]);
  129.     }
  130.     cout << Ans;
  132.     return 0;
  133. }

T3

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注