제출 #1290192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290192		boclobanchat	Grapevine (NOI22_grapevine)	C++20	100 / 100	246 ms	30720 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
struct edge { int l,r,v; };
struct segmenttree
{
	long long seg[MAXN*4],lazy[MAXN*4];
	void build(int l,int r,int pos)
	{
		seg[pos]=INF;
		if(l==r) return ;
		int mid=(l+r)/2;
		build(l,mid,pos*2);
		build(mid+1,r,pos*2+1);
	}
	void down(int pos)
	{
		long long val=lazy[pos];
		seg[pos*2]+=val,seg[pos*2+1]+=val;
		lazy[pos*2]+=val,lazy[pos*2+1]+=val;
		lazy[pos]=0;
	}
	void update(int l,int r,int i,long long val,int pos)
	{
		if(i<l||r<i) return ;
		if(l==r)
		{
			seg[pos]=val;
			return ;
		}
		int mid=(l+r)/2;
		down(pos);
		update(l,mid,i,val,pos*2);
		update(mid+1,r,i,val,pos*2+1);
		seg[pos]=min(seg[pos*2],seg[pos*2+1]);
	}
	void update(int l,int r,int u,int v,long long val,int pos)
	{
		if(v<l||r<u) return ;
		if(u<=l&&r<=v)
		{
			seg[pos]+=val,lazy[pos]+=val;
			return ;
		}
		int mid=(l+r)/2;
		down(pos);
		update(l,mid,u,v,val,pos*2);
		update(mid+1,r,u,v,val,pos*2+1);
		seg[pos]=min(seg[pos*2],seg[pos*2+1]);
	}
	long long get(int l,int r,int u,int v,int pos)
	{
		if(u<=l&&r<=v) return seg[pos];
		int mid=(l+r)/2;
		down(pos);
		if(v<=mid) return get(l,mid,u,v,pos*2);
		if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
		return min(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
	}
};
segmenttree s0,s1,s2;
edge E[MAXN];
long long fen[MAXN],W[MAXN];
vector<int> ds[MAXN],ds2[MAXN];
int dis[MAXN],sub[MAXN],L[MAXN],R[MAXN],L2[MAXN],R2[MAXN],dp[MAXN],root[MAXN],tdfs=0,tdfs2=-1,cnt=0;
bool ck[MAXN];
void update(int i,int n,long long val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
long long get(int i) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void dfs(int i,int pre)
{
	sub[i]=1;
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
		sub[i]+=sub[v];
	}
}
void dfs2(int i,int pre)
{
	L[i]=++tdfs,dp[i]=i;
	ds2[root[i]].push_back(i);
	int mx=-1,pos=0;
	for(auto v:ds[i]) if(v!=pre&&mx<sub[v]) mx=sub[v],pos=v;
	if(mx!=-1)
	{
		root[pos]=root[i];
		dfs2(pos,i);
		dp[i]=dp[pos];
	}
	for(auto v:ds[i]) if(v!=pre&&v!=pos)
	{
		root[v]=i;
		dfs2(v,i);
	}
	R[i]=tdfs;
}
void dfs3(int i,int pre)
{
	L2[i]=++tdfs2;
	for(auto v:ds2[i]) dfs3(v,i);
	R2[i]=tdfs2;
}
void updedge(int pos,long long val)
{
	val-=W[pos],W[pos]+=val;
	update(L[pos],tdfs,val);
	update(R[pos]+1,tdfs,-val);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	ds[l].push_back(r),ds[r].push_back(l);
    	E[i]={l,r,v};
	}
	dis[0]=-1;
	dfs(1,1);
	dfs2(1,1);
	dfs3(0,0);
	for(int i=1;i<n;i++)
	{
		int l=E[i].l,r=E[i].r;
		if(dis[l]>dis[r]) swap(l,r);
		updedge(r,E[i].v);
	}
	s0.build(1,n,1),s1.build(1,n,1),s2.build(1,n,1);
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int pos;
			cin>>pos;
			if(!cnt) cout<<"-1\n";
			else
			{
				long long ans=INF,d=get(L[pos]);
				while(pos)
				{
					ans=min(ans,s2.get(1,n,L[pos],R[pos],1)+d-get(L[pos])*2);
					ans=min(ans,d+s1.get(1,n,L[pos]-dis[pos]+dis[root[pos]]+1,L[pos],1));
					pos=root[pos];
				}
				cout<<ans<<"\n";
			}
		}
		else if(t==2)
		{
			int pos;
			cin>>pos;
			if(!ck[pos])
			{
				ck[pos]=true,cnt++;
				s2.update(1,n,L[pos],get(L[pos]),1);
				s0.update(1,n,L2[pos],get(L[pos]),1);
			}
			else
			{
				ck[pos]=false,cnt--;
				s2.update(1,n,L[pos],INF,1);
				s0.update(1,n,L2[pos],INF,1);
			}
			while(pos)
			{
				s1.update(1,n,L[pos],s0.get(1,n,L2[pos],R2[pos],1)-get(L[pos])*2,1);
				pos=root[pos];
			}
		}
		else
		{
			int l,r,v;
			cin>>l>>r>>v;
			if(dis[l]>dis[r]) swap(l,r);
			int w=v-W[r],pos=r;
			updedge(r,v);
			s2.update(1,n,L[pos],R[pos],w,1);
			s0.update(1,n,L2[pos],R2[dp[pos]],w,1);
			s1.update(1,n,L[pos],R[pos],-w,1);
			if(s2.get(1,n,L[pos],R[pos],1)<INF/67)
				while(pos=root[pos]) s1.update(1,n,L[pos],s0.get(1,n,L2[pos],R2[pos],1)-get(L[pos])*2,1);
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32