【聯合選講】「LibreOJ β Round #3」绯色 IOI（懸念）

題目

Description

胖頭魚從魚戲團逃脫後，被主人一路追捕，他慌不擇路地跑進了一顆n個節點的池子樹，池子樹的所有度數為1的點就是出口。

假如他現在在節點i，那麼每個時刻他能選擇向某個與目前點有邊的點遊過去。初始時刻主人可能召喚若幹丂風出現在若幹出口，他們的移動規則與胖頭魚相同。

胖頭魚會被抓到，有兩種情況：

(1)某時刻結束時，他與丂風在同一個點。（甚至這個點是出口）

(2)某時刻進行時，與丂風經過同一條邊。

當胖頭魚成功躲開丂風并走到出口時，他就自由了。

現在胖頭魚想知道，當他初始在1…n中每個點時，主人需要多少丂風才能抓到他。

為了讓你了解題意，以下資訊可能是有用的：

(1) 當胖頭魚選擇了某個出口作為起點時，主人隻需要一個丂風放在那就可以抓到他了。

(2) 很顯然，人數上界就是出口數量。

Input

第一行一個整數n表示點數，接下來n-1行每行兩個數表示一條邊。

Output

輸出n個整數，每一行表示當胖頭魚初始在第i個點時，主人需要派出多少丂風

Sample Input

7

1 2

1 3

3 4

3 5

4 6

5 7

Sample Output

3

1

思路

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=500077;
int n,m,T,Q,tot,tim,top,ccnt,tcnt,ans;
int a[N],b[N],h[N],ne[N<<1],to[N<<1],w[N<<1],rev[N<<1];
int vis[N],dsu[N],tag[N],typ[N<<1];
int in[N],out[N],fa[N],tr[N<<2],lz[N<<2],rt[N];
int st[N],id[N<<1],Lv[N],Rv[N];

void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int getdsu(int x) {return x==dsu[x]?x:dsu[x]=getdsu(dsu[x]);}

void pd(int i) 
{
	int l=i<<1,r=(i<<1)|1;
	tr[l]+=lz[i],tr[r]+=lz[i],lz[l]+=lz[i],lz[r]+=lz[i],lz[i]=0;
}
void ins(int l,int r,int s,int t,int i,int v) 
{
	if(l<=s&&t<=r) {lz[i]+=v,tr[i]+=v;return;}
	int mid=(s+t)>>1; if(lz[i]) pd(i);
	if(l<=mid) ins(l,r,s,mid,i<<1,v);
	if(mid+1<=r) ins(l,r,mid+1,t,(i<<1)|1,v);
	tr[i]=max(tr[i<<1],tr[(i<<1)|1]);
}
int query(int l,int r,int s,int t,int i) 
{
	if(l<=s&&t<=r) return tr[i];
	int mid=(s+t)>>1,re=0; if(lz[i]) pd(i);
	if(l<=mid) re=query(l,r,s,mid,i<<1);
	if(mid+1<=r) re=max(re,query(l,r,mid+1,t,(i<<1)|1));
	return re;
}
void work_tree(int t,int v) 
{
	int x=to[t],y=to[rev[t]];
	if(x==fa[y]) ins(in[y],out[y],1,tim,1,v);
	else ins(in[id[t]],out[id[t]],1,tim,1,v),ins(in[x],out[x],1,tim,1,-v);
}

void dfs_tree(int x,int rt,int las) 
{
	in[x]=++tim,fa[x]=las,vis[x]=1;
	for(int i=h[x]; i; i=ne[i])
		if(to[i]!=las)
			dfs_tree(to[i],rt,x),id[i]=id[rev[i]]=rt,typ[i]=typ[rev[i]]=1;
	out[x]=tim;
}
void ring(int x,int y,int no,int las) 
{
	fa[x]=las,vis[x]=1;
	if(x==y)
	{
		for(int i=1; i<=top; i++)
		{
			typ[st[i]]=2,Lv[ccnt]+=w[st[i]];
			typ[rev[st[i]]]=3,Rv[ccnt]+=w[rev[st[i]]];
		}
	}
	for(int i=h[x]; i; i=ne[i]) if(to[i]!=las&&i!=no&&i!=rev[no])
	{
		id[i]=id[rev[i]]=ccnt,typ[i]=4;
		st[++top]=i,ring(to[i],y,no,x),--top;
	}
}
void prework() 
{
	for(int i=1; i<=m; i++) 
	{
		if(vis[i]) continue;
		int k=getdsu(i);
		if(!tag[k]) dfs_tree(i,i,0),rt[++tcnt]=i;
		else 
		{
			++ccnt,ring(to[tag[k]],to[rev[tag[k]]],tag[k],0);
			id[tag[k]]=id[rev[tag[k]]]=ccnt;
			typ[tag[k]]=2,Lv[ccnt]+=w[tag[k]];
			if(tag[k]!=rev[tag[k]]) typ[rev[tag[k]]]=3,Rv[ccnt]+=w[rev[tag[k]]];
			ans+=max(Lv[ccnt],Rv[ccnt]);
		}
	}
	for(int i=1; i<=tot; i++)
		if(typ[i]==4) ans+=w[i];
		else if(typ[i]==1) work_tree(i,w[i]);
	for(int i=1; i<=tcnt; i++) ans+=query(in[rt[i]],out[rt[i]],1,tim,1);
}

void work() 
{
	Q=read(),printf("%d\n",ans);
	while(Q--) 
	{
		int x=read()-ans*T,y=read()-ans*T;
		if(typ[x]==0);
		else if(typ[x]==1) 
		{
			int kv=query(in[id[x]],out[id[x]],1,tim,1);
			work_tree(x,y-w[x]),w[x]=y;
			ans+=query(in[id[x]],out[id[x]],1,tim,1)-kv;
		}
		else if(typ[x]==2) 
		{
			int kv=max(Lv[id[x]],Rv[id[x]]);
			Lv[id[x]]+=y-w[x],w[x]=y;
			ans+=max(Lv[id[x]],Rv[id[x]])-kv;
		}
		else if(typ[x]==3) 
		{
			int kv=max(Lv[id[x]],Rv[id[x]]);
			Rv[id[x]]+=y-w[x],w[x]=y;
			ans+=max(Lv[id[x]],Rv[id[x]])-kv;
		}
		else if(typ[x]==4) ans+=y-w[x],w[x]=y;
		printf("%d\n",ans);
	}
}

int main()
{
	n=read(),m=read(),T=read();
	for(int i=0; i<n; i++) a[i]=read();
	for(int i=0; i<n; i++) b[i]=read();
	for(int i=1; i<=m; i++) dsu[i]=i;
	for(int i=0; i<n; i++) 
	{
		int x=(a[i]+b[i])%m+1,y=(a[i]-b[i]+m)%m+1;
		if(x>y) swap(x,y);
		add(y,x,read());
		int r1=getdsu(x),r2=getdsu(y);
		if(r1==r2) tag[r1]=tot;
		else dsu[r1]=r2,tag[r2]|=tag[r1];
		if(x!=y) rev[tot]=tot+1,rev[tot+1]=tot,add(x,y,read());
		else rev[tot]=tot;
	}
	prework(),work();
}