蒟蒻求助 样例能过 0pts
查看原帖
蒟蒻求助 样例能过 0pts
1206518
Nervegas楼主2024/9/12 07:32
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 10;

int f[maxn][20];
int de[maxn];
int dfn[maxn];//存储dfs序, 

int cnt, head[maxn];
int ans;
int dis[maxn];
set<int> st;
int vis[maxn];
struct node{
	int to;
	int nxt;
	int val;
}e[maxn];

void add(int u, int v, int c){
	e[++cnt].to = v;
	e[cnt].val = c;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

int dfs_clock;
int idf[maxn];

void dfs(int u, int fa, int w){
	de[u] = de[fa] + 1;
	dfn[u] = ++dfs_clock;
	dis[u] = dis[fa] + w;
	idf[dfs_clock] = u;
	f[u][0] = fa;
	for(int i = 1 ; i <= 16 ; i++){
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for(int i = head[u] ; i ; i = e[i].nxt){
		int v = e[i].to;
		int w = e[i].val;
		if(v != fa){
			dfs(v, u, w);
		}
	}
} 

signed lca(int u, int v){
	if(de[u] < de[v]){
		swap(u, v);
	}
	for(int i = 16 ; i >= 0 ; i--){
		if(de[f[u][i]] >= de[v]){
			u = f[u][i];
		}
	}
	if(u == v){
		return v;
	}
	for(int i = 16 ; i >= 0 ; i--){
		if(f[u][i] != f[v][i]){
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}

int n, m;
char op;
int x;

signed getdis(int u, int v){
	return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

set<int>::iterator it;


signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i < n ; i++){
    	int u, v, w;
    	cin >> u >> v >> w;
    	add(u, v, w);
    	add(v, u, w);
	}
	dfs(1, 0, 0);
	for(int i = 1 ; i <= m ; i++){
		cin >> x;
		x = dfn[x];
		if(vis[idf[x]] == 0){
			st.insert(x);
		}
		auto it1 = st.lower_bound(x);
		auto it2 = st.upper_bound(x);
		int y = idf[it1 == st.begin() ? *--st.end() : *--it1];//左边的那个dfs序 
		int z = idf[it2 == st.end() ? *st.begin() : *it2];//右边的那个dfs序 
		if(vis[idf[x]] == 1){
			st.erase(x);
		}
		x = idf[x];
		int d = getdis(x, y) + getdis(x, z) - getdis(y, z);
		if(vis[x] == 0){
			vis[x] = 1;
			ans += d;
		} 
		else{
			vis[x] = 0;
			ans -= d;
		}
		cout << ans << '\n';
	}
    return 0;
}

2024/9/12 07:32
加载中...