NC50468. 异象石
描述
输入描述
第一行有一个整数N，表示点的个数；
接下来N-1行每行三个整数x,y,z，表示点x和y之间有一条长度为z的双向边；
第N+1行有一个正整数M；
接下来M行每行是一个事件，事件是以下三种格式之一：
+x：表示点x上出现了异象石；
-x：表示点x上的异象石被摧毁；
?：表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。
输出描述
对于每个?事件，输出一个整数表示答案。
示例1
输入:
6 1 2 1 1 3 5 4 1 7 4 5 3 6 4 2 10 + 3 + 1 ? + 6 ? + 5 ? - 6 - 3 ?
输出:
5 14 17 10
Java 解法, 执行用时: 1655ms, 内存消耗: 70740K, 提交时间: 2021-09-04 14:01:24
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
public class Main {
static long mod = 1;
static class SegmentTree {
static int l;
static int r;
static long v;
static Node root;
static long cache[];
static void build(long f[]) {
cache = f;
root = new Node(0, f.length - 1);
}
static long query(int left, int right) {
l = left;
r = right;
return root.query();
}
static void add_range(int left, int right, long value) {
l = left;
r = right;
v = value;
root.add_range();
}
static void multi_range(int left, int right, long value) {
l = left;
r = right;
v = value;
root.multi_range();
}
static void set_range(int left, int right) {
l = left;
r = right;
// root.set_range();
}
static class Node {
// boolean seted;
long setv = 1;
long add = 0;
int left;
int right;
long min_value;
Node l_node;
Node r_node;
public Node(int l, int r) {
left = l;
right = r;
if (l == r) {
min_value = cache[l];
} else {
int mid = (l + r) >> 1;
l_node = new Node(l, mid);
r_node = new Node(mid + 1, r);
pollup();
}
}
private long query() {
if (l <= left && r >= right) {
return min_value;
} else if (l > right || r < left) {
return 0;
} else {
pushdown();
long v1 = l_node.query();
long v2 = r_node.query();
pollup();
return (v1 + v2) % mod;
}
}
private void add_range() {
if (l <= left && r >= right) {
add += v;
min_value += v * (right - left + 1);
} else if (l > right || r < left) {
return;
} else {
pushdown();
l_node.add_range();
r_node.add_range();
pollup();
}
}
private void multi_range() {
if (l <= left && r >= right) {
setv *= v;
add = add * v;
min_value = (min_value * v) % mod;
} else if (l > right || r < left) {
return;
} else {
pushdown();
l_node.multi_range();
r_node.multi_range();
pollup();
}
}
// private void set_range() {
// if (l <= left && r >= right) {
// seted = true;
// setv = v;
// add = 0;
// min_value = v;
// } else if (l > right || r < left) {
// return;
// } else {
// pushdown();
// l_node.set_range();
// r_node.set_range();
// pollup();
// }
// }
// first multi, then add
private void pushdown() {
if (setv != 1) {
l_node.setv *= setv;
r_node.setv *= setv;
l_node.min_value = l_node.min_value * setv % mod;
r_node.min_value = r_node.min_value * setv % mod;
l_node.add = l_node.add * setv;
r_node.add = r_node.add * setv;
setv = 1;
}
if (add != 0) {
l_node.add += add;
r_node.add += add;
l_node.min_value += add * (l_node.right - l_node.left + 1);
l_node.min_value %= mod;
r_node.min_value += add * (r_node.right - r_node.left + 1);
r_node.min_value %= mod;
add = 0;
}
}
private void pollup() {
min_value = (l_node.min_value + r_node.min_value) % mod;
}
}
}
static class Task {
public static String roundS(double result, int scale) {
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
long[][] mult(long a[][], long b[][], long mod) {
int l1 = a.length;
int l2 = b.length;
int l3 = b[0].length;
long r[][] = new long[l1][l3];
for (int i = 0; i < l1; ++i) {
for (int j = 0; j < l2; ++j) {
for (int k = 0; k < l3; ++k) {
r[i][k] = (r[i][k] + a[i][j] * b[j][k] % mod) % mod;
}
}
}
return r;
}
long[][] add(long a[][], long b[][], long mod) {
int l1 = a.length;
int l2 = a[0].length;
long r[][] = new long[l1][l2];
for (int i = 0; i < l1; ++i) {
for (int j = 0; j < l2; ++j) {
r[i][j] = (a[i][j] + b[i][j]) % mod;
}
}
return r;
}
long[][] ones(int len) {
long r[][] = new long[len][len];
for (int i = 0; i < len; ++i) {
r[i][i] = 1L;
}
return r;
}
long[][] quick(long a[][], int times, long mod) {
int len = a.length;
long ans[][] = ones(len);
while (times > 0) {
if ((times & 1) == 1) {
ans = mult(ans, a, mod);
}
a = mult(a, a, mod);
times >>= 1;
}
return ans;
}
long mb = 1535002967L;
long p = 1331;
long hash[];
long f[];
long getHash(int i, int l) {
// str from i to (i+len-1)
return (mb + (hash[i + l] - f[l] * hash[i]) % mb) % mb;
}
void hash(String s) {
int len = s.length();
hash = new long[len + 1];
f = new long[len + 1];
hash = new long[len + 1];
f[0] = 1;
for (int j = 1; j <= len; ++j) {
hash[j] = (hash[j - 1] * p + s.charAt(j - 1)) % mb;
f[j] = (f[j - 1] * p) % mb;
}
// for(int i=0;i<len;++i){
// for(int l = 0;i+l<=len;++l){
// long v = getHash(i,l);
// }
// }
}
void dfs(int rt) {
Stack<Integer> stk = new Stack<>();
stk.push(rt);
int num = 0;
while (!stk.isEmpty()) {
int cur = stk.pop();
adfn[num] = cur;
dfn[cur] = num++;
for (int to[] : g[cur]) {
if (to[1] != fa[cur][0]) {
fa[to[1]][0] = cur;
dep[to[1]] = dep[cur] + 1;
sd[to[1]] = sd[cur] + to[0];
stk.push(to[1]);
}
}
}
for (int j = 1; j <= 15; ++j) {
for (int p = 0; p < n; ++p) {
fa[p][j] = fa[fa[p][j - 1]][j - 1];
}
}
}
int fa[][];
List<int[]> g[];
int n;
int dep[];
long sd[];
int dfn[];
int adfn[];
int lca(int a, int b) {
if (dep[a] > dep[b]) {
int u = a;
a = b;
b = u;
}
// dep a <= dep b
int dis = dep[b] - dep[a];
for (int i = 0; i <= 17; ++i) {
if (dis << ~i < 0) {
b = fa[b][i];
}
}
if (a == b)
return a;
for (int i = 17; i >= 0; --i) {
if (fa[b][i] != fa[a][i]) {
b = fa[b][i];
a = fa[a][i];
}
}
return fa[a][0];
}
long dis(int n1,int n2){
if(n1==n2) return 0;
int f = lca(n1,n2);
return sd[n1] + sd[n2] - 2L* sd[f];
}
public void solve(int testNumber, InputReader in, PrintWriter out) {
n = in.nextInt();
g = new ArrayList[n];
fa = new int[n][20];
dep = new int[n];
sd = new long[n];
dfn = new int[n];
adfn = new int[n];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<>();
}
for (int j = 0; j < n - 1; ++j) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int w = in.nextInt();
g[u].add(new int[]{w,v});
g[v].add(new int[]{w,u});
}
dfs(0);
TreeSet<Integer> ts = new TreeSet<>();
int m = in.nextInt();
long rr = 0;
for (int i = 0; i < m; ++i) {
char tp; tp = in.nextChar();
if(tp=='+'){
int node = in.nextInt()-1;
int at = dfn[node];
if(ts.size()==0){
ts.add(at);
continue;
}
Integer m1 = ts.higher(at);
Integer m2 = ts.lower(at);
if(m1==null){
m1 = ts.first();
}
if(m2==null){
m2 = ts.last();
}
rr -= dis(adfn[m1],adfn[m2]);
rr += dis(adfn[m1],node);
rr += dis(node, adfn[m2]);
ts.add(at);
}else if(tp=='-'){
int node = in.nextInt()-1;
int at = dfn[node];
ts.remove(at);
if(ts.size()==0){
continue;
}
Integer m1 = ts.higher(at);
Integer m2 = ts.lower(at);
if(m1==null){
m1 = ts.first();
}
if(m2==null){
m2 = ts.last();
}
rr += dis(adfn[m1],adfn[m2]);
rr -= dis(adfn[m1],node);
rr -= dis(node, adfn[m2]);
}else{
out.println(rr/2L);
}
}
}
// int t = in.nextInt();
// int n = in.nextInt();
// int m = in.nextInt();
//
// ct = 0;
// h = new int[n];Arrays.fill(h,-1);
// if(t==1) {
// to = new int[m * 2];
// ne = new int[m * 2];
//
// fob = new boolean[m * 2];
// }else{
// to = new int[m];
// ne = new int[m];
//
// }
//
//
// int rd[] = new int[n];
// int cd[] = new int[n];
// li = new int[m];
// tp = m-1;
//
// int rt= 0;
//
// for(int i=0;i<m;++i){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// add(u,v);
// if(t==1){
// add(v,u);
// }
// cd[u]++;
// rd[v]++;
// rt = u;
// }
//
// if(t==2){
//
// for(int i=0;i<n;++i){
// if(rd[i]!=cd[i]){
// out.println("NO");return;
// }
// }
// }else{
//
// for(int i=0;i<n;++i){
// if(((rd[i]+cd[i])%2)>0){
// out.println("NO");return;
// }
// }
//
// }
//
//
//
// dfs11(rt, t);
//
//
//
// if(tp!=-1){
// out.print("NO");
// return;
// }
//
// out.println("YES");
//
// for(int i=0;i<m;++i){
// out.print(li[i]+ " ");
// }
// int f1[][] = new int[q][3];
//
// for(int i=0;i<q;++i){
// for(int j=0;j<3;++j){
// f1[i][j] = in.nextInt();
// }
// }
//
//
// int h[] = new int[n+1];
//
// Arrays.fill(h,-1);
//
//
// int ne[] = new int[p*2+q];
// int to[] = new int[p*2+q];
// int wt[] = new int[p*2+q];
// ct = 0;
// Func fk = (int x,int y,int z) -> {
// to[ct] = y;
// ne[ct] = h[x];
// wt[ct] = z;
// h[x] = ct++;
// };
//
// for(int i=0;i<p;++i){
// int u = f[i][0];
// int v = f[i][1];
//
//
//
//
// fk.add(u,v,f[i][2]);
// fk.add(v,u,f[i][2]);
// }
//
// for(int i=0;i<q;++i){
// int u = f1[i][0];
// int v = f1[i][1];
//
//
//
//
// fk.add(u,v,f1[i][2]);
// }
// int dp[] = new int[n+1];
// Arrays.fill(dp,100000000);
// dp[s] = 0;
//
//
// PriorityQueue<int[]> qu = new PriorityQueue<>(Comparator.comparingInt((x)->x[0]));
// qu.add(new int[]{0,s});
// while(qu.size()>0){
// int cc[] = qu.poll();
// int cur = cc[1];
// if(cc[0]!=dp[cur]) continue;
// for(int j = h[cur];j!=-1;j=ne[j]){
// int v = to[j];
// if(dp[v] > dp[cur] + wt[j]){
// dp[v] = dp[cur] + wt[j];
// qu.offer(new int[]{dp[v],v});
// }
// }
// }
//
// for(int j=1;j<=n;++j){
// if(dp[j]==100000000){
// out.println("NO PATH");
// }else{
// out.println(dp[j]);
// }
// }
// for(int t=0;t<5;++t) {
// int at = fi[t];
// dp[at][t] = 0;
// PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt((x) -> x[0]));
// q.offer(new int[]{0, at});
// while (q.size() > 0) {
// int cur[] = q.poll();
// if (cur[0] != dp[cur[1]][t]) continue;
// int i = cur[1];
// for (int j = h[i]; j != -1; j = ne[j]) {
// int v = to[j];
// if (dp[i][t] + wt[j] < dp[v][t]) {
// dp[v][t] = dp[i][t] + wt[j];
// q.offer(new int[]{dp[v][t], v});
// }
// }
// }
// }
// int cl[] = new int[]{0,1,2,3,4};
// int rs = Integer.MAX_VALUE;
// do{
// int s= dp[1][cl[0]];
// for(int j=0;j<4;++j){
// int nxt = fi[cl[j+1]];
// s += dp[nxt][cl[j]];
// }
// rs = Math.min(rs,s);
//
//
// }while(next_perm(cl));
//
// out.print(rs);
boolean next_perm(int[] a) {
int len = a.length;
for (int i = len - 2, j = 0; i >= 0; --i) {
if (a[i] < a[i + 1]) {
j = len - 1;
for (; a[j] <= a[i]; --j) ;
int p = a[j];
a[j] = a[i];
a[i] = p;
j = i + 1;
for (int ed = len - 1; j < ed; --ed) {
p = a[ed];
a[ed] = a[j];
a[j++] = p;
}
return true;
}
}
return false;
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 30)).start();
//solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++(g++ 7.5.0) 解法, 执行用时: 262ms, 内存消耗: 13688K, 提交时间: 2023-06-25 15:25:24
// https://ac.nowcoder.com/acm/problem/50468
#include <bits/stdc++.h>
#define DEBUG_
using namespace std;
using ll = long long;
const int N = 100005, D = 17;
int n, m, u, v, w, k, idx, maxd;
int st[N][D];
int h[N], dep[N], dfn[N];
ll far[N];
int e[N * 2], ne[N * 2], wei[N * 2];
void add(int u, int v, int w) {
++idx;
e[idx] = v;
ne[idx] = h[u];
wei[idx] = w;
h[u] = idx;
}
void dfs(int x, int f, int d, ll p) {
dep[x] = d;
far[x] = p;
dfn[x] = ++k;
st[x][0] = f;
for (int i = h[x]; i > 0; i = ne[i])
if (e[i] != f)
dfs(e[i], x, d + 1, p + wei[i]);
}
void build() {
for (int d = 1; d < maxd; ++d)
for (int x = 1; x <= n; ++x)
st[x][d] = st[st[x][d - 1]][d - 1];
}
int find(int x, int k) {
for (int d = 0; k; k >>= 1, ++d)
if (k & 1)
x = st[x][d];
return x;
}
int lca(int x, int y) {
if (dep[x] > dep[y]) {
swap(x, y);
}
y = find(y, dep[y] - dep[x]);
if (y == x) {
return x;
}
for (int d = maxd - 1; d >= 0; --d) {
if (st[x][d] != st[y][d]) {
x = st[x][d];
y = st[y][d];
}
}
return st[x][0];
}
ll dist(int a, int b) {
return far[a] + far[b] - far[lca(a, b)] * 2;
}
int bit_len(int x) {
int ans = 0;
for (; x; x >>= 1, ++ans);
return ans;
}
int main() {
scanf("%d", &n);
maxd = bit_len(n);
for (int i = 1; i < n; ++i) {
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
dfs(1, 1, 0, 0);
build();
scanf("%d", &m);
ll ans = 0;
set<pair<int, int>> vis;
#ifdef DEBUG
for (int i = 1; i <= n; ++i) printf("dfn[%d]=%d ", i, dfn[i]);
printf("\n");
#endif
for (int i = 0; i < m; ++i) {
string p;
cin >> p;
// scanf("%c", p);
u = p[0];
// cout << p << endl;
#ifdef DEBUG
printf("i=%d, u=%c\n", i, u);
#endif
if (u == '+' || u == '-') {
scanf("%d", &v);
pair<int, int> trgt = {dfn[v], v};
if (u == '+' && vis.empty()) {
vis.insert(trgt);
ans = 0;
continue;
}
if (u == '-' && vis.size() == 1) {
vis.erase(trgt);
ans = 0;
continue;
}
// vis must has at least one value
int is_side = 0, x1, x2;
auto it = vis.lower_bound(trgt), it1 = it, it2 = it;
if (u == '-') {
// v must exists
if (it == vis.begin()) {
is_side = 1;
x1 = next(it)->second;
x2 = vis.rbegin()->second;
} else if (next(it) == vis.end()) {
is_side = 1;
x1 = vis.begin()->second;
x2 = prev(it)->second;
} else {
is_side = 0;
x1 = prev(it)->second;
x2 = next(it)->second;
}
} else {
// v must not exists
if (it == vis.begin() || it == vis.end()) {
is_side = 1;
x1 = vis.begin()->second;
x2 = vis.rbegin()->second;
} else {
is_side = 0;
x1 = prev(it)->second;
x2 = it->second;
}
}
ll delta = dist(x1, v) + dist(x2, v) - dist(x1, x2);
// int f1 = lca(x1, v);
// int f2 = lca(x2, v);
// int f = (dep[f1] > dep[f2]) ? f1 : f2;
// ll delta = dist()
// ll delta = dist(f, v);
// if (is_side == 1) {
// delta += dist(f, lca(x1, x2));
// }
#ifdef DEBUG
// printf("(u==+)=%d, (u==-)=%d\n", u=='+', u=='-');
printf("v=%d | dep[x1=%d]=%d, dep[x2=%d]=%d\n", v, x1, dep[x1], x2, dep[x2]);
printf("f=%d, delta=%lld\n", f, delta);
printf("\n");
#endif
if (u == '+') {
ans += delta;
vis.insert(trgt);
} else {
ans -= delta;
vis.erase(trgt);
}
} else { // u == '?'
printf("%lld\n", ans / 2);
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 657ms, 内存消耗: 18528K, 提交时间: 2020-01-21 21:57:49
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
vector<pair<int, int>> G[MAXN];
int F[MAXN][20];
long long D[MAXN];
int H[MAXN];
int N, M;
int dfn[MAXN];
int id[MAXN];
int clk;
void dfs_lca(int s, int f, long long d) {
D[s] = d, H[s] = H[f] + 1, F[s][0] = f;
dfn[s] = ++clk, id[clk] = s;
for (int i = 0; i < 19; i++) F[s][i+1] = F[F[s][i]][i];
for (auto it: G[s]) if (it.first != f) dfs_lca(it.first, s, it.second+d);
}
int lca(int x, int y) {
if (H[x] < H[y]) swap(x, y);
for (int i = 19; i >= 0; i--) if (H[F[x][i]] >= H[y]) x = F[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--) if (F[x][i] != F[y][i]) x= F[x][i], y = F[y][i];
return F[x][0];
}
long long dis(int x, int y) {
return D[x] + D[y] - 2*D[lca(x, y)];
}
int main() {
cin >> N;
for (int i = 0; i < N - 1; i++) {
int x, y, z; cin >> x >> y >> z;
G[x].push_back({y, z});
G[y].push_back({x, z});
}
dfs_lca(1, 0, 0);
// cout << "Done" << endl;
set<int> S;
cin >> M;
// cout << "### " << M << endl;
long long tot = 0;
while (M--) {
string op; cin >> op;
if (op == "+" || op == "-") {
int x; cin >> x;
int xi = dfn[x];
if (op == "+") S.insert(xi);
auto it = S.find(xi);
int prei = it == S.begin()? *S.rbegin():*prev(it);
int nxti = next(it) == S.end()? *S.begin(): *next(it);
int pre = id[prei], nxt = id[nxti];
long long diff = - dis(pre, nxt) + dis(pre, x) + dis(x, nxt);
if (op == "+") tot += diff;
else tot -= diff;
if (op == "-") S.erase(xi);
} else {
cout << tot / 2 << endl;
}
}
}