HDU 5296 Annoying problem

迈不过友情╰ 2022-08-02 13:49 281阅读 0赞

这里写图片描述

这是用倍增法按照题解公式写的代码，除了题解的那种操作细节以及公式以外其他都是最简单的那种LCA…

  1. // whn6325689
  2. // Mr.Phoebe
  3. // http://blog.csdn.net/u013007900
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <cstring>
  8. #include <climits>
  9. #include <complex>
  10. #include <fstream>
  11. #include <cassert>
  12. #include <cstdio>
  13. #include <bitset>
  14. #include <vector>
  15. #include <deque>
  16. #include <queue>
  17. #include <stack>
  18. #include <ctime>
  19. #include <set>
  20. #include <map>
  21. #include <cmath>
  22. #include <functional>
  23. #include <numeric>
  24. #pragma comment(linker, "/STACK:1024000000,1024000000")
  26. using namespace std;
  28. #define eps 1e-9
  29. #define PI acos(-1.0)
  30. #define INF 0x3f3f3f3f
  31. #define LLINF 1LL<<62
  32. #define speed std::ios::sync_with_stdio(false);
  34. typedef long long ll;
  35. typedef unsigned long long ull;
  36. typedef long double ld;
  37. typedef pair<ll, ll> pll;
  38. typedef complex<ld> point;
  39. typedef pair<int, int> pii;
  40. typedef pair<pii, int> piii;
  41. typedef vector<int> vi;
  43. #define CLR(x,y) memset(x,y,sizeof(x))
  44. #define CPY(x,y) memcpy(x,y,sizeof(x))
  45. #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
  46. #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
  48. #define mp(x,y) make_pair(x,y)
  49. #define pb(x) push_back(x)
  50. #define lowbit(x) (x&(-x))
  52. #define MID(x,y) (x+((y-x)>>1))
  53. #define ls (idx<<1)
  54. #define rs (idx<<1|1)
  55. #define lson ls,l,mid
  56. #define rson rs,mid+1,r
  57. #define root 1,1,n
  59. template<class T>
  60. inline bool read(T &n)
  61. {
  62.     T x = 0, tmp = 1;
  63.     char c = getchar();
  64.     while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  65.     if(c == EOF) return false;
  66.     if(c == '-') c = getchar(), tmp = -1;
  67.     while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
  68.     n = x*tmp;
  69.     return true;
  70. }
  71. template <class T>
  72. inline void write(T n)
  73. {
  74.     if(n < 0)
  75.     {
  76.         putchar('-');
  77.         n = -n;
  78.     }
  79.     int len = 0,data[20];
  80.     while(n)
  81.     {
  82.         data[len++] = n%10;
  83.         n /= 10;
  84.     }
  85.     if(!len) data[len++] = 0;
  86.     while(len--) putchar(data[len]+48);
  87. }
  88. //-----------------------------------
  90. const int MAXN=100010;
  92. int dfn[MAXN],redfn[MAXN];
  93. int n,q,cnt;
  94. ll ans;
  96. struct Edge
  97. {
  98.     int to,next,c;
  99. }e[MAXN<<1];
  101. int head[MAXN],tot;
  102. int dis[MAXN],p[MAXN][22],dep[MAXN];
  104. std::set<int> s;
  105. std::set<int>::iterator it1;
  106. std::set<int, std::greater<int> > ss;
  107. std::set<int, std::greater<int> >::iterator it2;
  109. void init()
  110. {
  111.     tot=0;dis[1]=0;dep[1]=0;p[1][0]=1;cnt=0;
  112.     CLR(head,-1);s.clear();ss.clear();ans=0;
  113. }
  115. void addedge(int u,int v,int c)
  116. {
  117.     e[tot].to=v;
  118.     e[tot].c=c;
  119.     e[tot].next=head[u];
  120.     head[u]=tot++;
  121. }
  123. void dfs(int u,int fa=-1)
  124. {
  125.     dfn[u]=++cnt;
  126.     redfn[cnt]=u;
  127.     int v;
  128.     for(int i=1;i<20;i++)
  129.         p[u][i]=p[p[u][i-1]][i-1];
  130.     for(int i=head[u];~i;i=e[i].next)
  131.     {
  132.         v=e[i].to;
  133.         if(fa==v)   continue;
  134.         dep[v]=dep[u]+1;
  135.         dis[v]=dis[u]+e[i].c;
  136.         p[v][0]=u;
  137.         dfs(v,u);
  138.     }
  139. }
  141. int LCA(int u,int v)
  142. {
  143.     if(dep[u]>dep[v])   swap(u,v);
  144.     int hu=dep[u],hv=dep[v];
  145.     int tu=u,tv=v;
  146.     for(int det=hv-hu,i=0;det;det>>=1,i++)
  147.         if(det&1)
  148.             tv=p[tv][i];
  149.     if(tu==tv)  return tu;
  150.     for(int i=19;i>=0;i--)
  151.     {
  152.         if(p[tu][i]==p[tv][i])
  153.             continue;
  154.         tu=p[tu][i];
  155.         tv=p[tv][i];
  156.     }
  157.     return p[tu][0];
  158. }
  161. int main()
  162. {
  163.     freopen("data.txt","r",stdin);
  164.     int T,cas=1;
  165.     read(T);
  166.     while(T--)
  167.     {
  168.         init();
  169.         read(n),read(q);
  170.         int op,u,v,c;
  171.         for(int i=1;i<n;i++)
  172.         {
  173.             read(u),read(v),read(c);
  174.             addedge(u,v,c);addedge(v,u,c);
  175.         }
  176.         dfs(1);
  177.         printf("Case #%d:\n",cas++);
  178.         while(q--)
  179.         {
  180.             read(op),read(c);
  181.             if(op==1)
  182.             {
  183.                 if(s.empty())
  184.                 {
  185.                     printf("0\n");
  186.                     s.insert(dfn[c]);ss.insert(dfn[c]);
  187.                     continue;
  188.                 }
  189.                 if(s.find(dfn[c])!=s.end())
  190.                 {
  191.                     printf("%I64d\n",ans);
  192.                     continue;
  193.                 }
  194.                 it1=s.upper_bound(dfn[c]);
  195.                 it2=ss.upper_bound(dfn[c]);
  196.                 if(it1==s.end() || it2==ss.end())
  197.                     u=*s.begin(),v=*ss.begin();
  198.                 else
  199.                     u=*it1,v=*it2;
  200.                 u=redfn[u],v=redfn[v];
  201.                 ans += dis[c] - dis[LCA(u,c)] -dis[LCA(v,c)] + dis[LCA(u,v)];
  202.                 s.insert(dfn[c]);
  203.                 ss.insert(dfn[c]);
  204.             }
  205.             else
  206.             {
  207.                 if(s.find(dfn[c])==s.end())
  208.                 {
  209.                     printf("%I64d\n",ans);
  210.                     continue;
  211.                 }
  212.                 s.erase(dfn[c]);ss.erase(dfn[c]);
  213.                 if(s.empty())
  214.                 {
  215.                     printf("0\n");
  216.                     continue;
  217.                 }
  218.                 it1=s.upper_bound(dfn[c]);
  219.                 it2=ss.upper_bound(dfn[c]);
  220.                 if(it1==s.end() || it2==ss.end())
  221.                     u=*s.begin(),v=*ss.begin();
  222.                 else
  223.                     u=*it1,v=*it2;
  224.                 u=redfn[u],v=redfn[v];
  225.                 ans -= dis[c] - dis[LCA(u,c)] -dis[LCA(v,c)] + dis[LCA(u,v)];
  226.             }
  227.             printf("%I64d\n",ans);
  228.         }
  229.     }
  230.     return 0;
  231. }

用的也是倍增算LCA，但是有用到类似树链剖分那样在树上建一个线段树

  1. #include "iostream"
  2. #include "cstring"
  3. #include "cstdio"
  4. #include "vector"
  5. #define PB push_back
  6. #define MP make_pair
  7. #define F first
  8. #define S second
  9. using namespace std;
  10. const int N = 100010;
  11. vector<pair<int, int> > e[N];
  12. int weight[N];
  13. int t[N << 2];
  14. int f[N][21];
  15. int pos[N], lpos[N], rpos[N], level[N];
  16. int total;
  17. void build(int l, int r, int idx)
  18. {
  19.     t[idx] = 0;
  20.     if(l == r) return;
  21.     int m = (l + r) / 2;
  22.     build(l, m, idx << 1);
  23.     build(m + 1, r, idx << 1 | 1);
  24. }
  25. void dfs(int x, int pa, int dep)
  26. {
  27.     level[x] = dep;
  28.     int now = f[x][0] = pa;
  29.     for(int i = 0; now != -1 && f[now][i] != -1; ++ i){
  30.         f[x][i + 1] = f[now][i];
  31.         now = f[now][i];
  32.     }
  33.     lpos[x] = ++total;
  34.     pos[total] = x;
  35.     for(int i = 0; i < e[x].size(); ++ i){
  36.         int u = e[x][i].F;
  37.         int w = e[x][i].S;
  38.         if(u == pa) continue;
  39.         weight[u] = weight[x] + w;
  40.         dfs(u, x, dep + 1);
  41.     }
  42.     rpos[x] = total;
  43. }
  44. void update(int l, int r, int id, int v, int idx)
  45. {
  46.     if(l == r){
  47.         t[idx] += v;
  48.         return;
  49.     }
  50.     int m = (l + r) / 2;
  51.     if(m < id){
  52.         update(m + 1, r, id, v, idx << 1 | 1);
  53.     }else{
  54.         update(l, m, id, v, idx << 1);
  55.     }
  56.     t[idx] = t[idx << 1] + t[idx << 1 | 1];
  57. }
  58. int query(int l, int r, int L, int R, int idx)
  59. {
  60.     if(l >= L && r <= R) return t[idx];
  61.     int m = (l + r) / 2;
  62.     if(m < L) return query(m + 1, r, L, R, idx << 1 | 1);
  63.     else if(m >= R) return query(l, m, L, R, idx << 1);
  64.     else return query(l, m, L, m, idx << 1) + query(m + 1, r, m + 1, R, idx << 1 | 1);
  65. }
  66. int jump(int x, int step)
  67. {
  68.     int k = 0;
  69.     while(step){
  70.         if(step & 1) x = f[x][k];
  71.         step >>= 1;
  72.         k ++;
  73.     }
  74.     return x;
  75. }
  76. int n;
  77. int findlca(int x, int num)
  78. {
  79.     int l = 0, r = level[x];
  80.     while(l < r){
  81.         int m = (l + r) / 2;
  82.         int u = jump(x, m);
  83.         if(query(1, n, lpos[u], rpos[u], 1) >= num){
  84.             r = m;
  85.         }else{
  86.             l = m + 1;
  87.         }
  88.     }
  89.     return jump(x, l);
  90. }
  91. int find_element(int x)
  92. {
  93.     int l = lpos[x], r = rpos[x];
  94.     while(l < r){
  95.         int m = (l + r) / 2;
  96.         int u = query(1, n, l, m, 1);
  97.         if(u >= 1){
  98.             r = m;
  99.         }else{
  100.             l = m + 1;
  101.         }
  102.     }
  103.     return pos[l];
  104. }
  105. int getnum(int x)
  106. {
  107.     return query(1, n, lpos[x], rpos[x], 1);
  108. }
  109. int vis[N];
  110. int main(void)
  111. {
  112.     int num_tests, g = 0;
  113.     scanf("%d", &num_tests);
  114.     while(num_tests --){
  115.         total = 0;
  116.         printf("Case #%d:\n", ++ g);
  117.         int q, x, y, w;
  118.         scanf("%d %d", &n, &q);
  119.         for(int i = 1; i <= n; ++ i){
  120.             e[i].clear();
  121.         }
  122.         for(int i = 1; i < n; ++ i){
  123.             scanf("%d %d %d",&x, &y, &w);
  124.             e[x].PB(MP(y, w));
  125.             e[y].PB(MP(x, w));
  126.         }
  127.         build(1, n, 1);
  128.         memset(f, -1, sizeof(f));
  129.         memset(vis, 0, sizeof(vis));
  130.         weight[1] = 0;
  131.         dfs(1, -1, 0);
  132.         int num = 0;
  133.         int ans = 0;
  134.         for(int i = 1; i <= q; ++ i){
  135.             scanf("%d %d", &x, &y);
  136.             if(x == 1){
  137.                 if(vis[y]){
  138.                     cout << ans << '\n';
  139.                     continue;
  140.                 }
  141.                 vis[y] = 1;
  142.                 num ++;
  143.                 if(num <= 1){
  144.                     ans = 0;
  145.                 }else{
  146.                     int u = findlca(y, 1);
  147.                     int v = find_element(u);
  148.                     if(getnum(u) == num - 1){
  149.                         if(getnum(u) == getnum(v)){
  150.                             ans += weight[y] - weight[u];
  151.                             ans += weight[v] - weight[u];
  152.                         }else{
  153.                             int t = findlca(v, num - 1);
  154.                             if(t == u){
  155.                                 ans += weight[y] - weight[u];
  156.                             }else{
  157.                                 ans += weight[y] - weight[u];
  158.                                 ans += weight[t] - weight[u];
  159.                             }
  160.                         }
  161.                     }else{
  162.                         ans += weight[y] - weight[u];
  163.                     }       
  164.                 }
  165.                 update(1, n, lpos[y], 1, 1);
  166.             }else{
  167.                 if(!vis[y]){
  168.                     cout << ans << '\n';
  169.                     continue;
  170.                 }
  171.                 vis[y] = 0;
  172.                 num --;
  173.                 update(1, n, lpos[y], -1, 1);
  174.                 if(num <= 1){
  175.                     ans = 0;
  176.                 }else{
  177.                     int u = findlca(y, 1);
  178.                     int v = find_element(u);
  179.                     if(getnum(u) == num){
  180.                         int target = findlca(v, num);
  181.                         ans -= weight[y] - weight[u];
  182.                         ans -= weight[target] - weight[u];
  183.                     }else{
  184.                         ans -= weight[y] - weight[u];
  185.                     }
  186.                 }
  187.             }
  188.             cout << ans << '\n';
  189.         }
  190.     }
  191.     return 0;
  192. }

发表评论

表情：
评论列表 （有 0 条评论，281人围观）

还没有评论，来说两句吧...

相关阅读