QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205428#7563. Fun on Treeucup-team087#WA 1651ms93376kbC++2021.5kb2023-10-07 15:56:122023-10-07 15:56:12

Judging History

你现在查看的是最新测评结果

  • [2023-10-07 15:56:12]
  • 评测
  • 测评结果:WA
  • 用时:1651ms
  • 内存:93376kb
  • [2023-10-07 15:56:12]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t>
void pb(vc<t>&a,const vc<t>&b){
	a.insert(a.ed,all(b));
}

template<class t>
vc<t> cat(vc<t> a,const vc<t>&b){
	pb(a,b);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

bool dbg=false;

//内部でグラフをいじるから in,out を使うときは注意
//hei[v] -> heavy edge で潜っていった時,自分含めて何個あるか
//pe[v]: v->par[v] の辺の情報
//-有向木のときは上から下の辺を入れてる
//-無向木のときは下から上の辺を入れてる
//VERIFY: yosupo
//CF530F
//CodeChef Persistent Oak
//AOJ GRL5C
template<class E>
struct HLD{
	vvc<E> g;
	int n,rt,cnt;
	vi sub,in,out,par,head,dep,hei,ni;
	vc<E> pe;
	int dfs1(int v,int p,int d){
		par[v]=p;
		dep[v]=d;
		for(auto itr=g[v].bg;itr!=g[v].ed;itr++)
			if(*itr==p){
				pe[v]=*itr;
				g[v].erase(itr);
				break;
			}
		for(auto&e:g[v]){
			pe[e]=e;
			sub[v]+=dfs1(e,v,d+1);
			if(sub[g[v][0]]<sub[e])
				swap(g[v][0],e);
		}
		return sub[v];
	}
	void dfs2(int v,int h){
		in[v]=cnt++;
		head[v]=h;
		for(int to:g[v])
			dfs2(to,to==g[v][0]?h:to);
		out[v]=cnt;
		if(si(g[v]))hei[v]=hei[g[v][0]]+1;
	}
	HLD(){}
	HLD(const vvc<E>&gg,int rr):g(gg),n(g.size()),rt(rr),cnt(0),
		sub(n,1),in(n),out(n),par(n,-1),head(n),dep(n),hei(n,1),ni(n),
		pe(n){
		dfs1(rt,-1,0);
		dfs2(rt,rt);
		rep(i,n)ni[in[i]]=i;
	}
	int lca(int a,int b){
		while(head[a]!=head[b]){
			if(dep[head[a]]>dep[head[b]])
				swap(a,b);
			b=par[head[b]];
		}
		if(dep[a]>dep[b])
			swap(a,b);
		return a;
	}
	int len(int a,int b){
		return dep[a]+dep[b]-dep[lca(a,b)]*2;
	}
	bool asde(int a,int b){
		return in[a]<=in[b]&&out[b]<=out[a];
	}
	//UCUP 1-22 F
	int adv(int a,int d){
		if(hei[a]<=d)return -1;
		else return ni[in[a]+d];
	}
	//CF692F
	int getpar(int v,int len){
		assert(dep[v]>=len);
		int tar=dep[v]-len;
		while(1){
			int h=head[v];
			if(dep[h]<=tar){
				return ni[in[h]+(tar-dep[h])];
			}
			v=par[h];
		}
		assert(false);
	}
	//1st UCUP 13 G
	int jump(int a,int b,int d){
		int c=lca(a,b);
		if(d<=(dep[a]-dep[c])){
			return getpar(a,d);
		}else{
			d=(dep[a]+dep[b]-dep[c]*2)-d;
			assert(d>=0);
			return getpar(b,d);
		}
	}
	//XX Opencup GP of Korea
	//CF625 F
	//2020 Multi-Uni Contest Day5 G
	//CF415E
	//Universal Cup 2023 Stage 1 G
	vi index;
	//vs を含む virtual tree を返す
	//返すのは virtual tree に使われた頂点と,辺の集合
	//辺の端点は,virtual tree における番号
	//元の木における番号を virtual tree の頂点番号に写すのが,index という変数
	//辺は ch->par の順
	//virtual tree は行き掛け順で番号がついている
	//特に,頂点 0 が根になるようにできている
	//pair<vi,vc<pi>> tree_compress(vi vs){
	void tree_compress(vi&vs,vc<pi>&es){
		if(si(index)==0)index.resize(n);
		assert(index.size());
		auto comp = [&](int x,int y){
			return in[x] < in[y];
		};
		//sort(all(vs),comp);
		assert(is_sorted(all(vs),comp));
		vs.erase(unique(all(vs)),vs.ed);
		int k = vs.size();
		rep(i,k-1){
			vs.pb(lca(vs[i],vs[i+1]));
		}
		sort(all(vs),comp);
		vs.erase(unique(all(vs)),vs.ed);
		k = vs.size();
		rep(i,k) index[vs[i]] = i;
		es.clear();
		rng(i,1,k){
			int p = lca(vs[i-1],vs[i]);
			es.eb(i,index[p]);
		}
		//return mp(vs,es);
	}
	//assume a is desdendant of b
	//ex=true <=> exclude b
	template<class F>
	void subpath_work(int a,int b,bool ex,F f){
		while(1){
			if(head[a]==head[b]){
				f(in[b]+ex,in[a]+1);
				break;
			}else{
				int h=head[a];
				f(in[h],in[a]+1);
				a=par[h];
			}
		}
	}
	//KUPC2021E
	//パスに対する操作順に注意
	//euler-tour 順にしたときの区間に作用していることに注意
	//ex=true exclude lca(a,b) (=apply path edges)
	template<class F>
	void path_work(int a,int b,bool ex,F f){
		int c=lca(a,b);
		subpath_work(a,c,ex,f);
		subpath_work(b,c,true,f);
	}
	//root-v パス上で f(x)=true となる最も深い頂点を返す
	//CF857G
	template<class F>
	int find_lowest(int v,F f){
		while(v>=0){
			int h=head[v];
			if(!f(h)){
				v=par[h];
			}else{
				int l=0,r=dep[v]-dep[h]+1;
				while(r-l>1){
					const int mid=(l+r)/2;
					if(f(ni[in[h]+mid]))l=mid;
					else r=mid;
				}
				return ni[in[h]+l];
			}
		}
		return -1;
	}
};

//atcoder-library をまあまあコピーして使っている

//N() が単位元

//merge で片方が inactive のときはもう片方をそのまま返す,
//といったときに,lazy の情報までコピーして渡さないようにする

//クエリできる点が[0,s)だったのを[0,n)に変えた (UCUP1-21D)
//ch,max_rightは動くと思う
//ちゃんと test してないから assert とかが壊れたらごめん

//VERIFY:
//https://atcoder.jp/contests/practice2/tasks/practice2_k
template<class N,bool Beats=false>
struct seglazy{
	vc<N> x;
	int n,L,s;
	seglazy(){}
	template<class T>
	seglazy(const vc<T>& a){
		n=a.size();
		L=0;
		while((1<<L)<n)L++;
		s=1<<L;
		x.resize(s*2);
		rep(i,n)x[s+i]=N(a[i]);
		gnr(i,1,s)upd(i);
	}
	seglazy(int nn){
		n=nn;
		L=0;
		while((1<<L)<n)L++;
		s=1<<L;
		x.assign(s*2,N());
		gnr(i,1,s)upd(i);
	}
	void upd(int i){
		x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void push(int i){
		x[i].push(x[i*2],x[i*2+1]);
	}
	N composite(int l,int r){
		assert(0<=l&&l<=r&&r<=n);
		if(l==r)return N();
		
		l+=s;
		r+=s;
		
		for (int i = L; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r - 1) >> i);
		}
		
		N sml,smr;
		while (l < r) {
			if (l & 1) sml = N::merge(sml, x[l++]);
			if (r & 1) smr = N::merge(x[--r], smr);
			l >>= 1;
			r >>= 1;
		}

		return N::merge(sml, smr);
	}
	//UCUP1-21 D
	template<class F,class... Args>
	void ch_beats(int i,F f,Args&&... args){
		if((x[i].*f)(forward<Args>(args)...))return;
		push(i);
		ch_beats(i*2,f,forward<Args>(args)...);
		ch_beats(i*2+1,f,forward<Args>(args)...);
		upd(i);
	}
	template<class F,class... Args>
	void ch(int l, int r, F f,Args&&... args) {
		assert(0<=l&&l<=r&&r<=n);
		if (l == r) return;

		l+=s;
		r+=s;

		for (int i = L; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r - 1) >> i);
		}
		
		static int buf[2][30];
		int cnt[2]{};
		{
			int l2 = l, r2 = r;
			while (l < r) {
				if (l & 1){
					//(x[l++].*f)(forward<Args>(args)...);
					buf[0][cnt[0]++]=l++;
				}
				if (r & 1){
					//(x[--r].*f)(forward<Args>(args)...);
					buf[1][cnt[1]++]=--r;
				}
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}
		if constexpr(Beats){
			rep(i,cnt[0])ch_beats(buf[0][i],f,forward<Args>(args)...);
			per(i,cnt[1])ch_beats(buf[1][i],f,forward<Args>(args)...);
		}else{
			rep(i,cnt[0])(x[buf[0][i]].*f)(forward<Args>(args)...);
			per(i,cnt[1])(x[buf[1][i]].*f)(forward<Args>(args)...);
		}

		for (int i = 1; i <= L; i++) {
			if (((l >> i) << i) != l) upd(l >> i);
			if (((r >> i) << i) != r) upd((r - 1) >> i);
		}
	}
	template<class F,class... Args>
	void chall(F f,Args&&... args){
		if constexpr(Beats){
			ch_beats(1,f,forward<Args>(args)...);
		}else{
			(x[1].*f)(forward<Args>(args)...);
		}
	}
	N getall(){return x[1];}
	template <class F,class... Args> 
	pair<int,N> max_right(int l,F f,Args&&... args){
		assert(0<=l&&l<=n);
		if(l==n)return mp(n,N());
		l+=s;
		
		for (int i = L; i >= 1; i--) push(l >> i);
		N sm;
		assert((sm.*f)(forward<Args>(args)...));
		do {
			while (l % 2 == 0) l >>= 1;
			if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
				while (l < s) {
					push(l);
					l = (2 * l);
					N tmp=N::merge(sm,x[l]);
					if ((tmp.*f)(forward<Args>(args)...)) {
						sm = tmp;
						l++;
					}
				}
				return mp(l - s,sm);
			}
			sm = N::merge(sm, x[l]);
			l++;
		} while ((l & -l) != l);
		return mp(n,sm);
	}
	//XXI Opencup Krakow M
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		assert(0<=r&&r<=n);
        if(r==0)return mp(0,N());
        r+=s;
        for (int i = L; i >= 1; i--) push((r - 1) >> i);
        N sm;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
                while (r < s) {
                    push(r);
                    r = (2 * r + 1);
                    N tmp=N::merge(x[r],sm);
                    if ((tmp.*f)(forward<Args>(args)...)) {
                        sm = tmp;
                        r--;
                    }
                }
                return mp(r + 1 - s,sm);
            }
            sm = N::merge(x[r], sm);
        } while ((r & -r) != r);
        return mp(0,sm);
    }
	template<class F,class...Args>
	void point_change(int p,F f,Args&&...args){
		assert(0 <= p && p < n);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		(x[p].*f)(forward<Args>(args)...);
		for (int i = 1; i <= L; i++) upd(p >> i);
	}
	void point_merge(int p,const N&t){
		assert(0 <= p && p < n);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		x[p]=N::merge(x[p],t);
		for (int i = 1; i <= L; i++) upd(p >> i);
	}
	N point_get(int p){
		assert(0 <= p && p < n);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		return x[p];
	}
	void point_set(int p,N val){
		assert(0 <= p && p < n);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		x[p]=val;
		for (int i = 1; i <= L; i++) upd(p >> i);
	}
	void enumerater(int l,int r,int i,int b,int e,vc<N>&dst){
		if(e<=l||r<=b)
			return;
		if(l+1==r){
			dst.pb(x[i]);
			return;
		}
		push(i);
		int m=(l+r)/2;
		enumerater(l,m,i*2,b,e,dst);
		enumerater(m,r,i*2+1,b,e,dst);
	}
	void enumerate(int b,int e,vc<N>&dst){
		assert(0<=b&&b<=e&&e<=n);
		return enumerater(0,s,1,b,e,dst);
	}
};

//Range add,max
struct RAM{
	int lz,mx,idn;
	RAM(pi v=pi(-inf,-inf)):lz(0),mx(v.a),idn(v.b){}
	void add(int v){
		mx+=v;
		lz+=v;
	}
	void push(RAM&x,RAM&y){
		x.add(lz);
		y.add(lz);
		lz=0;
	}
	static RAM merge(RAM x,RAM y){
		return RAM(max(x.getm(),y.getm()));
	}
	pi getm(){return pi(mx,idn);}
};

void slv(){
	int n,q;cin>>n>>q;
	vi sul=readvi(n);
	vvc<int> torg(n);
	vi dist(n);
	rng(i,1,n){
		int p,w;cin>>p>>w;
		p--;
		torg[p].pb(i);
		dist[i]=w;
	}
	
	HLD<int> hld(torg,0);
	for(auto i:hld.ni)if(i)dist[i]+=dist[hld.par[i]];
	
	vc<pi> aini(n);
	rep(i,n)aini[hld.in[i]]=pi(dist[i]-sul[i],-i);
	
	vc<pi> cini(n);
	rep(i,n)cini[hld.in[i]]=pi(-dist[i]-sul[i],-i);
	
	seglazy<RAM> a(aini),c(cini);
	
	/*auto sub=[&](int v){
		return a.composite(hld.in[v],hld.out[v]).getm();
	};*/
	
	seglazy<RAM> b(n),d(n);
	auto updbd=[&](int v){
		if(si(hld.g[v])){
			pi z=a.composite(hld.out[hld.g[v][0]],hld.out[v]).getm();
			b.point_set(hld.in[v],z);
			d.point_set(hld.in[v],pi(z.a-dist[v]*2,z.b));
		}
	};
	rep(i,n)updbd(i);
	
	rep(_,q){
		int x,y,v;cin>>x>>y>>v;
		x--;y--;v=-v;
		a.ch(hld.in[y],hld.out[y],&RAM::add,v);
		b.ch(hld.in[y],hld.out[y],&RAM::add,v);
		c.ch(hld.in[y],hld.out[y],&RAM::add,v);
		d.ch(hld.in[y],hld.out[y],&RAM::add,v);
		while(1){
			int h=hld.head[y];
			int p=hld.par[h];
			if(p==-1)break;
			updbd(p);
			y=p;
		}
		
		pi ans=a.composite(hld.in[x],hld.out[x]).getm();
		ans.a-=dist[x];
		
		int off=0;
		while(1){
			int h=hld.head[x];
			
			auto work=[&](pi z,int w){
				chmax(ans,pi(z.a+w+off,z.b));
			};
			
			work(a.composite(hld.in[x],hld.in[x]+hld.hei[x]).getm(),
				-dist[x]);
			work(b.composite(hld.in[x]+1,hld.in[x]+hld.hei[x]).getm(),
				-dist[x]);
			work(c.composite(hld.in[h],hld.in[x]).getm(),
				+dist[x]);
			work(d.composite(hld.in[h],hld.in[x]).getm(),
				+dist[x]);
			
			int p=hld.par[h];
			if(p==-1)break;
			off+=dist[x]-dist[p];
			x=p;
		}
		print(-ans.b+1,ans.a);
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1)slv();
	}else{
		//int t;cin>>t;rep(_,t)
		slv();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3732kb

input:

6 6
1 1 4 5 1 4
1 5
2 0
3 2
4 1
5 6
3 2 -100000
1 2 100000
1 1 0
2 2 66
3 1 5
4 4 -3

output:

6 100005
6 10
6 10
1 4
1 -1
1 1

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

5 6
-10 0 2 -4 8
1 7
1 1
2 2
2 -2
1 1 100
2 1 -100
1 1 0
4 3 10
2 5 3
5 2 2

output:

4 -87
1 17
4 13
1 19
1 17
1 15

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

6 3
0 0 0 0 0 0
1 10
1 10
1 -100
4 10
4 11
1 1 0
4 1 0
1 4 1000

output:

2 10
6 11
2 10

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2 0
1 1
1 3

output:


result:

ok 0 lines

Test #5:

score: 0
Accepted
time: 1224ms
memory: 90960kb

input:

200000 200000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

119017 15000000000
120167 17000000000
119017 15000000000
119017 15000000000
120167 17000000000
120167 15000000000
120167 16000000000
119017 17000000000
119017 16000000000
119017 12000000000
119017 17000000000
120167 16000000000
120167 14000000000
120167 17000000000
120167 18000000000
120167 16000000...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 1651ms
memory: 93376kb

input:

200000 200000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

169355 88000000000
171273 95000000000
171273 100000000000
169355 88000000000
169355 93000000000
169355 97000000000
169355 93000000000
171273 78000000000
171273 86000000000
169355 90000000000
169355 84000000000
169355 80000000000
169355 78000000000
171273 84000000000
169355 89000000000
171273 8400000...

result:

ok 200000 lines

Test #7:

score: -100
Wrong Answer
time: 1181ms
memory: 90724kb

input:

200000 200000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

60406 17000000000
163359 19000000000
163359 18000000000
163359 17000000000
163359 18000000000
60406 17000000000
163359 16000000000
60406 16000000000
60406 18000000000
163359 17000000000
163359 16000000000
163359 15000000000
163359 18000000000
163359 16000000000
60406 13000000000
163359 15000000000
6...

result:

wrong answer 8733rd lines differ - expected: '94748 20057019021', found: '195257 19200172381'