萌新刚学 OI ,求助!!!
查看原帖
萌新刚学 OI ,求助!!!
414386
Isshiki·Iroha楼主2021/10/4 16:11

思路和兔队讲的不能说是很像,只能说是一模一样

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define ri reg int
using namespace std;
namespace Mashiro {
	char buf[1<<18],*p1=buf,*p2=buf;
	inline int getc() {
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
	}
#define getc() getchar()
	template<typename T>inline void read(T& x) {
		x=0;
		int f=1;
		char ch=getc();
		while(!isdigit(ch)) {
			if(ch=='-')f=~f+1;
			ch=getc();
		}
		while (isdigit (ch)) {
			x=(x<<3)+(x<<1)+(ch^48);
			ch=getc();
		}
		x*=f;
	}
	template <typename T,typename... Args> inline void read(T& x, Args&... args) {
		read(x);
		read(args...);
	}
	char buffer[1<<18];
	int p11=-1;
	const int p22=(1<<18)-1;
	inline void flush() {
		fwrite(buffer,1,p11+1,stdout),p11=-1;
	}
	inline void putc(const char &x) {
		if (p11==p22) flush();
		buffer[++p11]=x;
	}
	template<typename T>void write(T x) {
		static int buf[40],top=0;
		if(x<0)putc('-'),x=~x+1;
		while(x)buf[++top]=x%10,x/=10;
		if(top==0)buf[++top]=0;
		while (top) putc(buf[top--]^48);
		putc(' ');
		flush();
	}
	template <typename T,typename... Args> inline void write(T x, Args... args) {
		write(x);
		write(args...);
	}
}
using namespace Mashiro;
const int LogN=22;
const int maxn=1e5+10;
const int maxm=2e5+10;
int n,m;
int times=0;
int head[maxn],dfn[maxn],dep[maxn],anti_dfn[maxn];
bool baowu[maxn];
ll dis[maxn],ans=0;
int tot;
int f[maxn][LogN+1];
struct node {
	int v,nxt;
	ll w;
} kano[maxm];
inline void add_kano(ri u,ri v,ll w){
	++tot;
	kano[tot].nxt=head[u];
	kano[tot].v=v;
	kano[tot].w=w;
	head[u]=tot;
}
inline void dfs(ri u,ri fa){
	dfn[u]=++times;
	anti_dfn[times]=u;
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(ri i(head[u]);i;i=kano[i].nxt){
		ri v=kano[i].v;
		if(v==fa)continue;
		dis[v]=dis[u]+kano[i].w;
		dfs(v,u);
	}
}
inline void Pre(){
	for(ri i(1);i<=LogN;++i){
		for(ri j(1);j<=n;++j){
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
}
inline int lca(ri x,ri y){
	if(dep[x]<dep[y])swap(x,y);
	for(ri i(LogN);~i;--i){
		if(dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if(x==y)return x;
	for(ri i(LogN);~i;--i){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
inline ll dist(ri x,ri y){
	if(x==y)return 0ll;
	return dis[x]+dis[y]-(dis[lca(x,y)]<<1ll);
}
set<int>s;
typedef set<int>::iterator SI;
int main() {
	read(n,m);
	for(ri i(1),u,v,w;i<n;++i){
		read(u,v,w);
		add_kano(u,v,w);
		add_kano(v,u,w);
	}
	dfs(1,0);
	Pre();
	for(ri i(1),u,l,r;i<=m;++i){
		read(u);
		if(!baowu[u])s.insert(dfn[u]);

        SI it1=s.lower_bound(dfn[u]);
        if(it1==s.begin())it1=--s.end();
        else --it1;
        l=anti_dfn[*it1];

		SI it2=s.upper_bound(dfn[u]);
        if(it2==s.end())it2=s.begin();
        r=anti_dfn[*it2];

        ll temp=dist(u,l)+dist(u,r)-dist(l,r);
        if(!baowu[u])baowu[u]=1,ans+=temp;
        else baowu[u]=0,ans-=temp;

		write(ans);
		putc('\n');
	}
	return 0;
}
2021/10/4 16:11
加载中...