QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205428 | #7563. Fun on Tree | ucup-team087# | WA | 1651ms | 93376kb | C++20 | 21.5kb | 2023-10-07 15:56:12 | 2023-10-07 15:56:12 |
Judging History
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'