2 条题解
-
0
#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
#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
- 上传者