結果

問題 No.898 tri-βutree
ユーザー TqkTqk
提出日時 2019-11-25 01:43:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 679 ms / 4,000 ms
コード長 15,970 bytes
コンパイル時間 4,009 ms
コンパイル使用メモリ 228,616 KB
実行使用メモリ 29,444 KB
最終ジャッジ日時 2024-11-14 21:53:24
合計ジャッジ時間 18,005 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 203 ms
29,180 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 666 ms
29,324 KB
testcase_08 AC 664 ms
29,316 KB
testcase_09 AC 664 ms
29,324 KB
testcase_10 AC 659 ms
29,320 KB
testcase_11 AC 668 ms
29,320 KB
testcase_12 AC 659 ms
29,312 KB
testcase_13 AC 655 ms
29,316 KB
testcase_14 AC 655 ms
29,216 KB
testcase_15 AC 667 ms
29,312 KB
testcase_16 AC 654 ms
29,312 KB
testcase_17 AC 659 ms
29,316 KB
testcase_18 AC 679 ms
29,320 KB
testcase_19 AC 669 ms
29,324 KB
testcase_20 AC 661 ms
29,316 KB
testcase_21 AC 666 ms
29,444 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:211:8: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  211 | mint<> operator""m(const unsigned long long n){ return mint<>(n); }
      |        ^~~~~~~~
main.cpp:212:17: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  212 | mint<998244353> operator""m9(const unsigned long long n){ return mint<998244353>(n); }
      |                 ^~~~~~~~
main.cpp:213:15: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
  213 | mint<1000003> operator""m3(const unsigned long long n){ return mint<1000003>(n); }
      |               ^~~~~~~~

ソースコード

diff # 

//sub-BOF
//#define _AOJ_

        /*vvv>
        zzzzzI
 .---.  zzuzuI                 .vgggg&,.
+++++=  dAC:|I  .WbbWo       JMM9^```?TMB`  ..&gNNg,.   gggggggJ,   qgggggggg] (&&&&&&&&[   c+OA&J,   (&&&&&&+J,   .cJeAA&-.  (&&&&&&&&x   .&AA&=-.
+++++=  dTqk|I  Xpbpbp      JM#`           (M#^   ?MMp  MM|   +TMN. JMF      ' |yk      ` dVY    7Vk,  Vy     XV  cVf     ?Y!  JM         V$      `
+++++=  dcf:|I  Xppppp      dMN           .MM+     .MM  MM|     MM] JMMMMMM+   |@tqkoh)  ,y0      (V$  yyyyyyyV7  VV           JMWyZWr    TWVVVVW&,
++++++  d7qk|0  Xppppp      ^HMN,    _.db  WMm,   .MMF  MM|   ..MM` JMF      . |yk       .WV&.   .XW'  yy   4yn.  jyn      +.  JM                #S
`++++`  ?ZZZX=  ?WWWW=        -THMMMMH9^    (TMMMMM9!   MMMMMMM""   JMMMMMMMME |UU.        ?TUUUUY=    UU.   (UU-  ^7TUUUV7!   JUUUUUUUU  7TUNKO*/

#pragma region template

#pragma region basic
#pragma GCC optimize ("O3")//#pragma GCC optimize ("fast-math")
#pragma GCC target ("avx2")
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef long double ld;
typedef string cs;
#pragma endregion

#pragma region rep
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define per(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__))
#define each(c) for(auto &e:c)
#pragma endregion

#pragma region io
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
template<class T>
ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }

#ifdef __ENV_TQK__
#include<Windows.h>
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
inline void in(){ SetConsoleTextAttribute(hConsole,10); }
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){
	SetConsoleTextAttribute(hConsole,15);
	cin>>head;in(move(tail)...);
}
#else
inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
#endif

inline bool out(){ return(cout<<'\n',0); }
template <class T>
inline bool out(T t){ return(cout<<t<<'\n',0); }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }
template <class T>
inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); }
#define alc alloc
#pragma endregion

#pragma region TA
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define vvin(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define all(v) v.begin(),v.end()
#define pb push_back
#define fi e.first
#define se e.second
#define YES(c) cout<<((c)?"YES\n":"NO\n"),0
#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0
#define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0
#define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0
#define o(p) cout<<p<<endl,0
#define sp(p) cout<<p<<" ",0
#define no(p) cout<<p,0
#define psort(l,r) if(l>r)swap(l,r);
inline constexpr lint gcd(lint a,lint b){ if(!a||!b)return 0;while(b){ lint c=b;b=a%b;a=c; }return a; }
template<typename T>
inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; }
template<typename T>
inline constexpr bool chmax(T &mx,const T &cnt){ if(mx<cnt){ mx=cnt;return 1; } else return 0; }
#define ve(type) vector<type>
#define fn(ty1,ty2,ex) [](ty1 a,ty2 b){ return(ex); }
#define lfn(ex) [](lint a,lint b){ return(ex); }
#pragma endregion

#pragma region other
#ifdef __ENV_TQK__
#define deb(...) out(__VA_ARGS__)
#define dsp(ex) sp(ex)
#define dno(ex) no(ex)
#else
#define deb(...) 0
#define dsp(ex) 0
#define dno(ex) 0
#endif
struct Fastio{
	Fastio(){
		cin.tie(0),cout.tie(0);
		ios::sync_with_stdio(0);
		cout<<fixed<<setprecision(10);
	}
} __fastio;
#pragma endregion

#pragma region mint
#define md_tmp template<uint_fast64_t md=1000000007>
md_tmp class mint{
	using u64=uint_fast64_t;

public:
	u64 a;

	constexpr mint(const u64 x=0) noexcept: a(x%md){}
	constexpr u64 &value() noexcept{ return a; }
	constexpr const u64 &value() const noexcept{ return a; }
	constexpr mint operator+(const mint rhs) const noexcept{
		return mint(*this)+=rhs;
	}
	constexpr mint operator-(const mint rhs) const noexcept{
		return mint(*this)-=rhs;
	}
	constexpr mint operator*(const mint rhs) const noexcept{
		return mint(*this)*=rhs;
	}
	constexpr mint operator^(const lint rhs) const noexcept{
		return mint(*this)^=rhs;
	}
	constexpr mint operator/(const mint rhs) const noexcept{
		return mint(*this)/=rhs;
	}
	constexpr mint &operator+=(const mint rhs) noexcept{
		a+=rhs.a;
		if(a>=md)a-=md;
		return *this;
	}
	constexpr mint &operator-=(const mint rhs) noexcept{
		if(a<rhs.a)a+=md;
		a-=rhs.a;
		return *this;
	}
	constexpr mint &operator*=(const mint rhs) noexcept{
		a=a*rhs.a%md;
		return *this;
	}
	constexpr mint &operator^=(const lint rhs) noexcept{
		if(!rhs)return *this=1;
		u64 exp=rhs-1;
		mint base=this->a;
		while(exp){
			if(exp&1)*this*=base;
			base*=base;
			exp>>=1;
		}
		return *this;
	}
	constexpr mint &operator/=(const mint rhs) noexcept{
		a=(*this*(rhs^(md-2))).a;
		return *this;
	}
};
md_tmp istream& operator>>(istream& os,mint<md>& m){
	os>>m.a,m.a%=md;
	return os;
}
md_tmp ostream& operator<<(ostream& os,const mint<md>& m){
	return os<<m.a;
}
md_tmp mint<md> ncr(lint n,lint r){
	if(n<r||n<0||r<0)return mint<md>(0);
	mint<md>ncr_res=1,ncr_div=1;
	rep(r)ncr_res*=(n-i),ncr_div*=(r-i);
	return ncr_res/ncr_div;
}
#ifndef _AOJ_
mint<> operator""m(const unsigned long long n){ return mint<>(n); }
mint<998244353> operator""m9(const unsigned long long n){ return mint<998244353>(n); }
mint<1000003> operator""m3(const unsigned long long n){ return mint<1000003>(n); }
#endif
#pragma endregion

#pragma region P
class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; };
istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; }
constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }
constexpr bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }
constexpr bool operator<=(const P& l,const P& r){ return!(l.f-r.f?l.f>r.f:l.s>r.s); }
constexpr bool operator>=(const P& l,const P& r){ return!(l.f-r.f?l.f<r.f:l.s<r.s); }
#pragma endregion

#pragma endregion

#pragma region const
#define linf 1152921504606846976
//#define inf linf
#define MAXN 101010
#define md_1e9_7 1000000007
#define md_998244353 998244353
#define pi 3.14159265358979323846
//#define mod md_1e9_7
const int d4[5]={0,1,0,-1,0};
#pragma endregion

using length=lint;//info an edge has
struct edge{
	int src,to;
	length cost;

	edge(){}
	edge(int to,length cost): src(-1),to(to),cost(cost){}
	edge(int src,int to,length cost): src(src),to(to),cost(cost){}
	edge &operator=(const int &x){
		to=x;
		return *this;
	}
	operator int() const{ return to; }
};
istream& operator>>(istream& os,edge& e){ os>>e.src>>e.to>>e.cost;return os; }

using Matrix=vector<vector<length> >;
using Edges=vector<edge>;
using Weighted=vector<Edges>;
using UnWeighted=vector<vector<int> >;

// HLD( <tree> , root )
// === .build() ===
// .fold(hi, lo, func, inclusive)
//   where func(l, r) proceeds with [l, r)
// === O(1) ===
// .in(a) : in-time of Euler Tour : alias = .[a]
// .out(a) : out-time of Euler Tour
// .rev(a) : rev[in[a]] = a
// .head(a) : ascend all light edges
// .tail(a) : descend all heavy edges
// ---
// .subtree_size(a)
// .depth(a) : 0-indexed
// .parent(a) : -1 if [a] is root
// .heavy(a) : [a] cannot be a leaf. return the node opposite of the heavy edge
// === O(log n) ===
// .climb(a)
// .descendTo(from, to, steps)
// .steps(a, b)
// === --- ===
// for subtree : [ .in(a)           , .out(a) )
// (exclusive) : [ .in_exclusive(a) , .out(a) )
// HL-Decomposition {{{
// based on Euler Tour
struct HLD{
public:
	using size_type = std::size_t;
	using graph_type = std::vector< std::vector< int > >;

private:
	size_type n;
	std::vector< size_type > hd,tl;
	std::vector< size_type > sub;
	std::vector< size_type > dep;
	std::vector< int > par;
	std::vector< size_type > vid;
	size_type root;
	graph_type tree;

public:
	HLD(): n(0){}
	HLD(size_type n,size_type root = 0)
		: n(n),hd(n),tl(n),sub(n),dep(n),par(n),vid(n),tree(n){
		setRoot(root);
	}
	HLD(const graph_type &tree,size_type root): HLD(tree.size(),root){
		this->tree = tree;
	}

	void setRoot(size_type root){
		assert(root < n);
		this->root = root;
	}

private:
	bool built = 0;
	std::vector< size_type > vid_rev;

public:
	void build(){
		assert(!built && n);
		built = 1;

		vid_rev.resize(n);

		hd[root] = root;
		dfs0();
		dfs1();
		for(size_type i = 0; i < n; i++) vid_rev[vid[i]] = i;
	}

private:
	void dfs0(){
		std::vector< int > used(n);
		std::vector< std::tuple< size_type,int,size_type > > stk;
		stk.reserve(n);
		stk.emplace_back(root,-1,0);
		while(stk.size()){
			size_type i,d;
			int p;
			std::tie(i,p,d) = stk.back();
			if(!used[i]){
				used[i] = 1;
				par[i] = p;
				dep[i] = d;
				for(auto &j : tree[i])
					if(j != p){
						stk.emplace_back(j,i,d + 1);
					}
			} else{
				stk.pop_back();
				sub[i] = 1;
				for(auto &j : tree[i])
					if(j != p){
						if(sub[j] > sub[tree[i].back()]){
							std::swap(tree[i].back(),j);
						}
						sub[i] += sub[j];
					}
				if(tree[i].back() != p){
					tl[i] = tl[tree[i].back()];
				} else{
					tl[i] = i;
				}
			}
		}
	}
	void dfs1(){
		std::vector< int > used(n);
		std::vector< std::tuple< size_type,int > > stk;
		stk.reserve(n);
		stk.emplace_back(root,-1);
		size_type id = 0;
		while(stk.size()){
			size_type i;
			int p;
			std::tie(i,p) = stk.back(),stk.pop_back();
			vid[i] = id++;
			for(auto j : tree[i])
				if(j != p){
					hd[j] = j == tree[i].back() ? hd[i] : j;
					stk.emplace_back(j,i);
				}
		}
	}

public:
	size_type operator[](size_type i) const{ return in(i); }
	size_type in(size_type i) const{
		assert(built);
		assert(i < n);
		return vid[i];
	}
	size_type in_exclusive(size_type i) const{ return in(i) + 1; }
	size_type out(size_type i) const{
		assert(built);
		assert(i < n);
		return vid[i] + sub[i];
	}
	size_type out_exclusive(size_type i) const{ return out(i) - 1; }
	size_type head(size_type i) const{
		assert(built);
		return hd.at(i);
	}
	size_type tail(size_type i) const{
		assert(built);
		return tl.at(i);
	}
	size_type rev(size_type i) const{
		assert(built);
		return vid_rev.at(i);
	}
	size_type subtree_size(size_type i) const{
		assert(built);
		return sub.at(i);
	}
	size_type depth(size_type i) const{
		assert(built);
		return dep.at(i);
	}
	int parent(size_type i) const{
		assert(built);
		return par.at(i);
	}
	size_type steps(size_type a,size_type b) const{
		assert(built);
		assert(a < n && b < n);
		return dep[a] + dep[b] - 2 * dep[lca(a,b)];
	}
	size_type climb(size_type a,long long t) const{
		assert(built);
		assert(a < n && t >= 0);
		while(t){
			long long c = std::min< long long >(vid[a] - vid[hd[a]],t);
			t -= c;
			a = vid_rev[vid[a] - c];
			if(t && a != root){
				t--;
				a = par[a];
			}
			if(a == root) break;
		}
		return a;
	}
	size_type descendTo(size_type from,size_type to,long long steps) const{
		assert(built);
		assert(steps >= 0);
		assert(from < n && to < n);
		return climb(to,dep[to] - dep[from] - steps);
	}
	void add_edge(size_type a,size_type b){
		assert(built);
		assert(a < n && b < n);
		tree[a].emplace_back(b);
		tree[b].emplace_back(a);
	}
	size_type lca(size_type a,size_type b) const{
		assert(built);
		assert(a < n && b < n);
		while(1){
			if(vid[a] > vid[b]) std::swap(a,b);
			if(hd[a] == hd[b]) return a;
			b = par[hd[b]];
		}
	}
	size_type heavy(size_type a) const{
		assert(built);
		assert(a < n);
		assert(tree[a].back() != par[a]);
		return tree[a].back();
	}
	void _fold_vertex(size_type hi,int lo,std::function< void(int,int) > f,
					  bool inclusive) const{
		assert(built);
		assert(hi < n && 0 <= lo && lo < (int)n);
		while(lo != -1 && dep[lo] >= dep[hi]){
			size_type nex = max(vid[hd[lo]],vid[hi]);
			f(nex + (nex == vid[hi] && !inclusive),vid[lo] + 1);
			lo = par[hd[lo]];
		}
	}
	void _fold_edge(size_type hi,int lo,std::function< void(int,int) > f) const{
		assert(built);
		assert(hi < n && 0 <= lo && lo < (int)n);
		while(lo != -1 && dep[lo] >= dep[hi]){
			size_type nex = max(vid[hd[lo]],vid[hi]);
			f(nex+(nex==vid[hi]),vid[lo]+1);
			lo = par[hd[lo]];
		}
	}
	void fold_path_vertex(int s,int t,std::function< void(int,int) > f) const{
		int l=lca(s,t);
		_fold_vertex(l,s,f,1);
		_fold_vertex(l,t,f,0);
	}
	void fold_path_edge(int s,int t,std::function< void(int,int) > f) const{
		int l=lca(s,t);
		_fold_edge(l,s,f);
		_fold_edge(l,t,f);
	}
	void fold_subtree_vertex(int i,std::function< void(int,int) > f) const{
		f(in(i),out(i));
	}
	void fold_subtree_edge(int i,std::function< void(int,int) > f) const{
		f(in(i)+1,out(i));
	}

	size_type distance(size_type a,size_type b) const{
		return depth(a)+depth(b)-2*depth(lca(a,b));
	}
	size_type size() const{ return n; }
};
// }}}

class Ushi{
public:
	using T=lint;
	using func=function<T(T,T)>;

	int n,sz;
	vector<lint> node;

	func f;
	T e;

	Ushi(vector<T> v,func f,T e):f(f),e(e){
		sz=v.size();n=1;
		while(n<sz)n<<=1;
		node.resize(2*n,e);
		rep(i,sz)node[n+i]=v[i];
		for(int i=n-1;i>0;--i)node[i]=f(node[2*i],node[2*i+1]);
	}
	T* at(int i){ return &node[i+n]; }//use like *tree.at(i)=x,tree.adjust(i);
	void adjust(int i){
		i+=n;while(i>>=1)node[i]=f(node[2*i],node[2*i+1]);
	}
	T fold(int a,int b,int k=1,int l=0,int r=-1){
		if(r<0)r=n;
		if(r<=a||b<=l)return e;
		if(a<=l&&r<=b)return node[k];
		return f(fold(a,b,2*k,l,(l+r)/2),fold(a,b,2*k+1,(l+r)/2,r));
	}
};//verified(DSL_2_A,DSL_2_B):http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3604788#1

int main(){
	lint n,u,v,w;in(n);
	UnWeighted g(n);
	map<P,lint> _len;
	vector<lint>len(n);//after hld

	rep(n-1){
		in(u,v,w); psort(u,v);
		g[u].pb(v),g[v].pb(u);
		_len[P(u,v)]=w;
	}
	HLD h(g,0);h.build();
	rep(i,1,n){
		int u=h.parent(i),v=i; psort(u,v);
		len[h.in(i)]=_len[P(u,v)];
	}
	Ushi ki(len,[](lint a,lint b){return a+b;},0);
	//end-input

	lint q;in(q);
	while(q--){
		lint x,y,z,ans=0;in(x,y,z);
		{
			lint d1=h.depth(h.lca(x,y)),d2=h.depth(h.lca(y,z)),d3=h.depth(h.lca(z,x));
			if(d2>d1&&d2>d3)swap(x,z); else if(d3>d1&&d3>d2)swap(y,z);
		}
		h.fold_path_edge(x,y,         [&](int l,int r){ans+=ki.fold(l,r);});
		h.fold_path_edge(z,h.lca(x,y),[&](int l,int r){ans+=ki.fold(l,r);});
		out(ans);
	}
}

//sub-EOF
0