Powered by:NEFU AB-IN

P2146 [NOI2015] 软件包管理器

• 题意

  
  

  简而言之，根节点为$0$，其余所有节点都只有唯一的一个父节点

  • $install$，加载一个节点，问需要先加载多少个它所依赖的节点
  • $uninstall$，卸载一个节点，问当它被卸载时多少个节点会被牵连

• 思路

  当把树建好之后，这就是一个裸的树剖

  • $install$，加载节点，查询它到根节点$0$这一段节点们中，有多少个$0$，并全赋值为$1$，可以用线段树维护
  • $uninstall$，卸载一个节点，即它的为$1$的子节点有多少个，这个可以用$dfs$序加上它的$size$完成

  注意两个点

  • 虽然板子是线段树加法的板子，但我们要做的不是累加，而是覆盖，即权值覆盖
  • 将判断是否有懒标记改为$?1$，因为$0$也有用，代表卸载

• 代码

  #include <bits/stdc++.h>
  using namespace std;
  #define LL long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                      \
      ios::sync_with_stdio(false); \
      cin.tie(0);                  \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  #define ls i << 1
  #define rs i << 1 | 1
  typedef pair<int, int> PII;
  
  const int N = 20;
  struct Edge
  {
      int v, ne;
  } e[N << 2];
  int h[N];
  int cnt;
  void add(int u, int v)
  {
      e[cnt].v = v;
      e[cnt].ne = h[u];
      h[u] = cnt++;
  }
  void init()
  {
      memset(h, -1, sizeof(h));
      cnt = 0;
  }
  
  namespace TreeChain
  {
      int w[N];
      int pre[N], sizx[N], son[N], deep[N];
      int dfn[N], top[N], a[N];
      int cnx; // dfs2 pool
  
      void dfs1(int u, int fa)
      {
          pre[u] = fa;
          deep[u] = deep[fa] + 1;
          sizx[u] = 1;
          int maxson = -1;
          for (int i = h[u]; ~i; i = e[i].ne)
          {
              int v = e[i].v;
              if (v != fa)
              {
                  dfs1(v, u);
                  sizx[u] += sizx[v];
                  if (maxson < sizx[v])
                  {
                      maxson = sizx[v];
                      son[u] = v;
                  }
              }
          }
      }
  
      void dfs2(int u, int t)
      {
          top[u] = t;
          dfn[u] = ++cnx;
          a[cnx] = w[u];
          if (!son[u])
              return;
          dfs2(son[u], t);
          for (int i = h[u]; ~i; i = e[i].ne)
          {
              int v = e[i].v;
              if (v != pre[u] && v != son[u])
              {
                  dfs2(v, v);
              }
          }
      }
  }
  using namespace TreeChain;
  
  namespace xds_add
  {
      LL a[N << 2], tr[N << 2], add_tag[N << 2], k;
      int n, x, y;
  
      inline void pushup(int i)
      {
          tr[i] = tr[ls] + tr[rs];
      }
  
      void build(int i, int l, int r)
      {
          add_tag[i] = -1;
          if (l == r)
          {
              tr[i] = a[l];
              return;
          }
          int mid = (l + r) >> 1;
          build(ls, l, mid);
          build(rs, mid + 1, r);
          pushup(i);
      }
  
      inline void ADD(int i, int l, int r, LL k)
      {
          // 在ADD函数中将 += 改为 =
          add_tag[i] = k; 
          tr[i] = (r - l + 1) * k;
      }
  
      inline void pushdown(
  

  上一篇：弓虽子：pku2992（约数，素因子分解）

  下一篇：没有了