2 条题解

  • 0
    @ 2025-10-8 16:57:08
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N = 1e5 + 10;
    vector<pair<int, int>> G[N];
    set<pair<int, int>> S;
    int tsp, dfn[N], D, f[N][20], dep[N]; LL d[N];
    
    void dfs(int x, int fa) {
        dfn[x] = ++tsp; dep[x] = dep[fa] + 1;
        f[x][0] = fa; for (int i = 1; i <= D; i++) f[x][i] = f[f[x][i-1]][i-1];
        for (auto i : G[x]) {
            int y = i.first, c = i.second; if (y == fa) continue;
            d[y] = d[x] + c;
            dfs(y, x);
        }
    }
    
    int LCA(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        for (int i = D; i >= 0; i--) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
        if (x == y) return x;
        for (int i = D; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    
    LL getd(int x, int y) { return d[x] + d[y] - 2 * d[LCA(x, y)]; }
    
    int main() {
        int n; scanf("%d", &n);
        for (int i = 1, x, y, c; i < n; i++) {
            scanf("%d%d%d", &x, &y, &c);
            G[x].push_back({y, c}); G[y].push_back({x, c});
        }
        int m; scanf("%d", &m);
        tsp = 0; memset(dfn, 0, sizeof(dfn)); memset(d, 0, sizeof(d));
        D = log2(n); dep[0] = 0; dfs(1, 0);
        LL ans = 0;
        for (int i = 1, x; i <= m; i++) {
            char s[5]; scanf("%s", s);
            if (s[0] == '?') printf("%lld\n", ans / 2);
            else {
                scanf("%d", &x);
                if (s[0] == '+') {
                    if (S.empty()) { S.insert({dfn[x], x}); continue; }
                } else {
                    S.erase({dfn[x], x});
                    if (S.empty()) continue;
                }
                auto t = S.lower_bound({dfn[x], x}), r = t, l = --t;
                if (r == S.begin() || r == S.end()) l = S.begin(), r = --S.end();
                LL a = getd(l->second, r->second);
                LL b = getd(x, l->second) + getd(x, r->second);
                if (s[0] == '+') { ans += b - a; S.insert({dfn[x], x}); }
                else ans += a - b;
            }
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:56:57
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=1e5+10;
      vector<pair<int,int>>G[N];
      set<pair<int, int>> S; 
      int tsp,dfn[N], D,f[N][20],dep[N]; LL d[N];
      void dfs(int x, int fa)
      {
          dfn[x]=++tsp; dep[x]=dep[fa]+1; 
      	f[x][0]=fa;for(int i=1; i<=D; i++) f[x][i]=f[f[x][i-1]][i-1];
          for(auto i:G[x])
          {
              int y=i.first,c=i.second; if(y==fa) continue;
              d[y]=d[x]+c; 
              dfs(y, x);
          }
      }
      int LCA(int x, int y)
      {
          if(dep[x]<dep[y]) swap(x, y);
          for(int i=D; i>=0; i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
          if(x==y) return x;
          for(int i=D; i>=0; i--) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
          return f[x][0];
      }
      LL getd(int x, int y) {return d[x]+d[y]-2*d[LCA(x, y)];}
      int main()
      {
          int n; scanf("%d", &n); 
          for(int i=1,x,y,c; i<n; i++)
          {
              scanf("%d%d%d", &x, &y, &c);
              G[x].push_back({y,c});G[y].push_back({x,c});
          }
          int m; scanf("%d", &m);
          tsp=0; memset(dfn, 0, sizeof(dfn)); memset(d, 0, sizeof(d));
          D=log2(n);dep[0]=0; dfs(1, 0); 
      	LL ans=0;
          for(int i=1,x; i<=m; i++)
          {
              char s[5]; scanf("%s", s);
              if(s[0]=='?') printf("%lld\n", ans/2);
              else
              {
                  scanf("%d", &x);
                  if(s[0]=='+')
                  {
                      if(S.empty()) {S.insert({dfn[x], x}); continue;}
                  }
                  else
                  {
                      S.erase({dfn[x], x});
                      if(S.empty()) continue;
                  }
                  auto t=S.lower_bound({dfn[x], x}), r=t, l=--t;
                  if(r==S.begin()||r==S.end()) l=S.begin(),r=--S.end();
                  LL a=getd(l->second, r->second);
                  LL b=getd(x, l->second)+getd(x, r->second); 
                  if(s[0]=='+') {ans+=b-a; S.insert({dfn[x], x});} 
                  else ans+=a-b;
              }
          }
          return 0;
      }
      • 1

      信息

      ID
      1443
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      77
      已通过
      21
      上传者