Submission #465565

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }


struct Node {
	static long long pathUpdateCount, treeUpdateCount;
	static long long pathPropagateCount, treePropagateCount;

	Node *pathLeft, *pathRight;			//path tree
	Node *siblingLeft, *siblingRight;	//sibling tree
	Node *topChild;						//path treeからsibling treeへ
	Node *parent;						//path/sibling treeの両方で用いられる
	bool reversed;						//evertのために、パスにだけ遅延伝播させる。path-localなlazinessの例としても
	int weight;							//頂点属性の例として
	long long pathWeightSum;			//path-localな情報
	long long treeWeightSum;			//entire-treeの情報
	ll maxDistLeft, maxDistRight;		//パスの左端・右端の頂点からの最大の距離(高さ)+1 (頂点の数で数える)
	ll maxDistSiblingLeft;				//sibling tree中のパスの頭からの最大の距離の最大値
	ll maxDistSiblingRight;			//reverseのために左右両方の場合を保持しておく
	ll sndDistSiblingLeft;				//diameterのために最大だけでなくsnd maxまでも保持しておく必要がある
	ll sndDistSiblingRight;			//1つしか無い場合は0とする

	Node()
		: pathLeft(NULL), pathRight(NULL)
		, siblingLeft(NULL), siblingRight(NULL)
		, topChild(NULL), parent(NULL)
		, reversed(false)
		, weight(0), pathWeightSum(0), treeWeightSum(0)
		, maxDistLeft(0), maxDistRight(0)
		, maxDistSiblingLeft(0), maxDistSiblingRight(0)
		, sndDistSiblingLeft(0), sndDistSiblingRight(0)
		{ }

	inline Node *&path(bool lr) { return !lr ? pathLeft : pathRight; }
	inline Node *&sibling(bool lr) { return !lr ? siblingLeft : siblingRight; }
	inline Node *&child(bool ps, bool lr) { return !ps ? path(lr) : sibling(lr); }

	static long long getNodePathWeightSum(const Node *a) {
		return a->pathWeightSum;
	}
	static long long getNodeTreeWeightSum(const Node *a) {
		return a->treeWeightSum;
	}

	static ll getNodeMaxDistLR(const Node *a, bool lr) {
		return !(lr ^ a->reversed) ? a->maxDistLeft : a->maxDistRight;
	}
	static ll getNodeMaxDistSibling(const Node *a) {
		return !a->reversed ? a->maxDistSiblingLeft : a->maxDistSiblingRight;
	}
	static ll getNodeSndDistSibling(const Node *a) {
		return !a->reversed ? a->sndDistSiblingLeft : a->sndDistSiblingRight;
	}

	static inline void assignMax(ll &x, ll y) {
		if(x < y) x = y;
	}
	static inline void assignMaxSnd(ll &fst, ll &snd, ll y) {
		if(fst < y) {
			snd = fst;
			fst = y;
		}else if(snd < y) {
			snd = y;
		}
	}

	void treeUpdate() {
		treeUpdateCount ++;

		Node *a = this;
		long long treeWeightSum = a->weight;
		//+1は頂点aの分
		ll leftSum = a->weight + (a->pathLeft != NULL ? a->pathLeft->pathWeightSum : 0);
		ll rightSum = a->weight + (a->pathRight != NULL ? a->pathRight->pathWeightSum : 0);
		ll maxDistLeft = leftSum, maxDistRight = rightSum;
		ll maxDistSibling = 0, sndDistSibling = 0;

		if(a->pathLeft) {
			treeWeightSum += getNodeTreeWeightSum(a->pathLeft);
			assignMax(maxDistLeft, getNodeMaxDistLR(a->pathLeft, false));
			assignMax(maxDistRight, rightSum + getNodeMaxDistLR(a->pathLeft, true));
		}
		if(a->pathRight) {
			treeWeightSum += getNodeTreeWeightSum(a->pathRight);
			assignMax(maxDistLeft, leftSum + getNodeMaxDistLR(a->pathRight, false));
			assignMax(maxDistRight, getNodeMaxDistLR(a->pathRight, true));
		}
		if(a->topChild) {
			treeWeightSum += getNodeTreeWeightSum(a->topChild);
			ll childrenMaxDist = getNodeMaxDistSibling(a->topChild);
			assignMax(maxDistLeft, leftSum + childrenMaxDist);
			assignMax(maxDistRight, rightSum + childrenMaxDist);
		}
		if(a->siblingLeft) {
			treeWeightSum += getNodeTreeWeightSum(a->siblingLeft);
			assignMaxSnd(maxDistSibling, sndDistSibling, getNodeMaxDistSibling(a->siblingLeft));
			assignMaxSnd(maxDistSibling, sndDistSibling, getNodeSndDistSibling(a->siblingLeft));
		}
		if(a->siblingRight) {
			treeWeightSum += getNodeTreeWeightSum(a->siblingRight);
			assignMaxSnd(maxDistSibling, sndDistSibling, getNodeMaxDistSibling(a->siblingRight));
			assignMaxSnd(maxDistSibling, sndDistSibling, getNodeSndDistSibling(a->siblingRight));
		}

		a->treeWeightSum = treeWeightSum;
		a->maxDistLeft = maxDistLeft;
		a->maxDistRight = maxDistRight;

		a->maxDistSiblingLeft = a->maxDistSiblingRight = maxDistSibling;
		a->sndDistSiblingLeft = a->sndDistSiblingRight = sndDistSibling;
		assignMaxSnd(a->maxDistSiblingLeft, a->sndDistSiblingLeft, maxDistLeft);
		assignMaxSnd(a->maxDistSiblingRight, a->sndDistSiblingRight, maxDistRight);
	}

	void pathAndTreeUpdate() {
		pathUpdateCount ++;

		Node *a = this;
		int pathSize = 1;
		long long pathWeightSum = a->weight;
		if(a->pathLeft) {
			pathWeightSum += getNodePathWeightSum(a->pathLeft);
		}
		if(a->pathRight) {
			pathWeightSum += getNodePathWeightSum(a->pathRight);
		}
		a->pathWeightSum = pathWeightSum;

		a->treeUpdate();
	}

	void treePropagate() {
		treePropagateCount ++;
	}

	void pathAndTreePropagate() {
		pathPropagateCount ++;

		Node *a = this;
		if(a->reversed) {
			std::swap(a->pathLeft, a->pathRight);
			std::swap(a->maxDistLeft, a->maxDistRight);
			std::swap(a->maxDistSiblingLeft, a->maxDistSiblingRight);
			if(a->pathLeft) a->pathLeft->reversed ^= true;
			if(a->pathRight) a->pathRight->reversed ^= true;
			a->reversed = false;
		}

		a->treePropagate();
	}
};
long long Node::pathUpdateCount, Node::treeUpdateCount;
long long Node::pathPropagateCount, Node::treePropagateCount;


//template<typename Node>
class DynamicTree {
private:
	static inline bool isLocalRoot(const Node *a, bool ps) {
		return !a->parent || (a->parent->child(ps, false) != a && a->parent->child(ps, true) != a);
	}

	static void propagateNode(Node *a, bool ps) {
		if(!ps) a->pathAndTreePropagate();
		else a->treePropagate();
	}

	//aまでのパス上をトップダウンに遅延伝播させる。type=0なら根から、type=1ならpathの根から、type=2ならsiblingの根から
	static void topdownMain(Node *a, int type) {
		Node *r = a, *q = a->parent;
		while(q != NULL) {
			if(type == 1 && (q->pathLeft != r && q->pathRight != r)) break;
			if(type == 2 && (q->siblingLeft != r && q->siblingRight != r)) break;
			Node *p = q;
			q = p->parent;
			//どっちの子から来たかをparentにメモしちゃう
			p->parent = r;
			r = p;
		}
		while(r != a) {
			Node *c = r->parent;	//メモしておいた子
			r->parent = q;			//メモに書き換えたものを戻す
			q = r;
			propagateNode(r, type == 2);
			r = c;
		}
		propagateNode(a, type == 2);
	}

	static void globalTopdown(Node *a) {
		topdownMain(a, 0);
	}
	//path treeの根からaまでのパス上をトップダウンに遅延伝播させる
	static void pathTopdown(Node *a) {
		topdownMain(a, 1);
	}
	static void siblingTopdown(Node *a) {
		topdownMain(a, 2);
	}

	static void updateNode(Node *a, bool ps) {
		if(!ps) a->pathAndTreeUpdate();
		else a->treeUpdate();
	}
	
	//updateはrotate関数内ではしない
	static void rotate(Node *a, bool ps, bool lr) {
		Node *p = a->parent, *g = p->parent, *c = a->child(ps, lr);
		if(p->child(ps, !lr) = c) c->parent = p;
		a->child(ps, lr) = p; p->parent = a;
		if(a->parent = g) {
			if(g->pathLeft == p) g->pathLeft = a;
			else if(g->pathRight == p) g->pathRight = a;
			else if(g->topChild == p) g->topChild = a;
			else if(g->siblingLeft == p) g->siblingLeft = a;
			else if(g->siblingRight == p) g->siblingRight = a;
		}
	}

	//siblingのリンクをつけかえる
	static void moveSiblingLinks(Node *a, Node *g) {
		if(a->siblingLeft = g->siblingLeft) a->siblingLeft->parent = a;
		if(a->siblingRight = g->siblingRight) a->siblingRight->parent = a;
		g->siblingLeft = g->siblingRight = NULL;
	}

	//aを根からのパスの一部にしてさらにそのpath treeの根にする。
	//また、ps = false のときはsiblingをつなげすことも同時に行う。
	//a～globalな根のパスの全てのpropagateはこれを呼ぶ前に済ませておく。
	//lastupdate = trueの場合はこの時点でaはupdateされている必要がある。
	//lastupdate = falseの場合はaをupdateしない。
	static void localSplay(Node *a, bool ps, bool lastupdate = true) {
		if(isLocalRoot(a, ps)) return;
		//不変条件＆事後条件:
		//	・aから根へのパス以外のlocal tree上のノードは全てupdateされている
		//		(aを含むlocal tree以外のノードには関与しない。たとえlocal treeの根の親ノードでもupdateされていない場合がある)
		//	・aからglobalな根へのパスのノードは全てpropagateされている
		while(true) {
			Node *p = a->parent;
			bool plr = p->child(ps, true) == a;
			if(isLocalRoot(p, ps)) {
				if(!ps) moveSiblingLinks(a, p);
				rotate(a, ps, !plr);
				updateNode(a->child(ps, !plr), ps);
				break;
			}else {
				Node *g = p->parent;
				bool glr = g->child(ps, true) == p;
				bool groot = isLocalRoot(g, ps);
				
				if(groot && !ps) moveSiblingLinks(a, g);
				if(plr == glr) {
					rotate(p, ps, !plr);
					rotate(a, ps, !plr);
					updateNode(p->child(ps, !plr), ps);
					updateNode(p, ps);
				}else {
					rotate(a, ps, glr);
					rotate(a, ps, plr);
					updateNode(a->child(ps, plr), ps);
					updateNode(a->child(ps, !plr), ps);
				}
				if(groot) break;
			}
		}
		if(lastupdate) updateNode(a, ps);
	}

	//aからlocal treeの根へのパスはpropagateされている必要がある
	static void localPathSplay(Node *a, bool lastupdate = true) {
		localSplay(a, false, lastupdate);
	}
	//aからlocal treeの根へのパスはpropagateされている必要がある
	static void localSiblingSplay(Node *a, bool lastupdate = true) {
		localSplay(a, true, lastupdate);
	}
	
	//aはsplay・propagateされている必要がある。
	//lastupdate = trueのときaはupdateされている必要がある。
	//lastupdate = falseのときa,hはupdateされない。
	static Node *pathHead(Node *a, bool lr = false, bool lastupdate = true) {
		assert(isLocalRoot(a, false));
		Node *h = a;
		while(true) {
			Node *c = h->path(lr);
			if(!c) break;
			c->pathAndTreePropagate();
			h = c;
		}
		localPathSplay(h, lastupdate);	//降りた分払う
		return h;
	}

	//aの属するpath treeをaの右側の位置で切ってtopChildとする。
	//aはpath tree上でsplayされている必要がある。
	static void splitPath(Node *a) {
		assert(isLocalRoot(a, false));
		Node *r = a->pathRight, *c = a->topChild;
		if(r != NULL) {
			a->pathRight = NULL;
			a->topChild = r;
			assert(r->siblingLeft == NULL && r->siblingRight == NULL);
			if(r->siblingLeft = c) {
				c->parent = r;
				r->treeUpdate();
			}
			a->pathAndTreeUpdate();
		}
	}

	//sibling tree上でaを削除する(切り離す)。
	//aはsibling tree上でsplayされている必要がある。
	//aからglobal treeの根のパスはpropagateされている必要がある。
	//lastupdate = falseのときはaもaの親もupdateしない。
	static void deleteChild(Node *a, bool lastupdate = true) {
		Node *r = a->siblingLeft;
		if(!r) {
			Node *p = a->parent;
			if(r = a->siblingRight) r->parent = p;
			if(p != NULL) {
				p->topChild = r;
				if(lastupdate) p->treeUpdate();
			}
		}else {
			r->treePropagate();
			while(r->siblingRight) {
				r = r->siblingRight;
				r->treePropagate();
			}
			localSiblingSplay(r, false);
			assert(r->siblingRight == a && !a->siblingLeft);
			Node *b = a->siblingRight;
			if(r->siblingRight = b) b->parent = r;
			r->treeUpdate();
		}
		a->siblingLeft = a->siblingRight = a->parent = NULL;
		if(lastupdate) a->treeUpdate();
	}

public:
	//aをglobal treeの根に持っていく。
	//aのlazinessも解消される。
	static void expose(Node *a) {
		globalTopdown(a);
		if(!a->parent) return;
		while(true) {
			localPathSplay(a, false);
			localSiblingSplay(a, false);
			Node *p = a->parent;
			if(!p) break;
			assert(p->topChild == a);
			Node *h = pathHead(a, false, false);
			//この時点ではaもhもupdateされていないことに注意する。
			assert(p->topChild == h);
			//パスの頭(h)とパスの親(p)を接合する。pの下側は切り離される
			localPathSplay(p, false);
			Node *r = p->pathRight;
			//hのsiblingsをどこに移すか。rがある場合はそこに移す。そうでない場合は
			if(r != NULL) {
				r->treePropagate();
				p->topChild = r;
				if(r->siblingLeft = h->siblingLeft) r->siblingLeft->parent = r;
				if(r->siblingRight = h->siblingRight) r->siblingRight->parent = r;
				h->siblingLeft = h->siblingRight = NULL;
				r->treeUpdate();
			}else {
				deleteChild(h, false);
			}
			p->pathRight = h;
			h->parent = p;
			//localPathSplayするのでここでのupdateは必要ない
		}
		a->pathAndTreeUpdate();
	}

public:
	static void directedLink(Node *a, Node *p) {
		//aをpのtopChildにする。pのexposeはentire-treeのlazinessのために必要
		expose(a); expose(p);
		assert(a->parent == NULL);
		Node *c = p->topChild;
		p->topChild = a;
		a->parent = p;
		if(a->siblingLeft = c) c->parent = a;
		a->treeUpdate();
		p->treeUpdate();
	}

	//aから根への方向の辺(親との辺)を切り、aの親を返す。aが根である場合は何もせず、NULLを返す。
	//返り値はexposeされているとは限らないので注意。
	static Node *directedCut(Node *a) {
		//aのpathLeft(根へ向かう方向)を単に切り離す
		expose(a);
		Node *l = a->pathLeft;
		if(l != NULL) {
			a->pathLeft = NULL;
			l->parent = NULL;
			a->pathAndTreeUpdate();
		}
		return l;
	}

	static bool isConnected(Node *a, Node *b) {
		if(a == b) return true;
		expose(a);
		expose(b);
		return a->parent != NULL;	//同じ木ならaが変更されてるはず
	}

	static Node *getTreeRoot(Node *a) {
		expose(a);
		return pathHead(a);
	}

	//返り値はexpose(propagate)されているとは限らないので注意。
	static Node *lca(Node *a, Node *b) {
		//a,bの順にexposeすることによって、bのパスからaのパスが分かれる場所がlcaとなる。
		//a,bが同一のパス上にある場合のためにbのsplitPathをしておく。
		if(a == b) return a;
		expose(a);
		expose(b);
		splitPath(b);
		if(a->parent == NULL) return NULL;	//同じ木ならaが変更されてるはず
		while(1) {
			localPathSplay(a);
			if(!a->parent) return a;
			localSiblingSplay(a);
			a = a->parent;
		}
	}

	//exposeがされた状態になっている。ただしpropagateはされていないので注意
	static void evert(Node *a) {
		//右側は子にしてから左側のパスを反転させる
		expose(a);
		splitPath(a);
		a->reversed ^= true;
	}

	static void link(Node *a, Node *b) {
		//aを根にしてからaをbのtopChildにする
		evert(a); expose(b);
		assert(a->parent == NULL);
		Node *c = b->topChild;
		b->topChild = a;
		a->parent = b;
		if(a->siblingLeft = c) c->parent = a;
		a->treeUpdate();
		b->treeUpdate();
	}

	static void cut(Node *a, Node *b) {
		//aを根にしてbの左側を切る。bのexposeはentire-treeのlazinessのために必要
		evert(a);
		expose(b);
		Node *l = b->pathLeft;
		assert(l == a);
		b->pathLeft = NULL;
		l->parent = NULL;
		b->pathAndTreeUpdate();
	}

	//bを見ればa→bのパスが見られるようにする。aを根にしてa→bのパスをexposeして右をsplitする。
	//ただし木の形を変えてしまうので必要なら根を元に戻す処理が必要。そのために元の木の根を返す。
	static Node *exposePath(Node *a, Node *b) {
		evert(a);
		a->pathAndTreePropagate();
		Node *orgRoot = pathHead(a, true);
		expose(b);
		assert(a == b || a->parent != NULL);	//連結性チェック
		splitPath(b);
		return orgRoot;
	}

	friend struct DynamicTreeDebugCheck;
};

typedef DynamicTree Tree;


struct NodeOps {
	static int getWeight(Node *a) {
		Tree::expose(a);
		return a->weight;
	}

	static void setWeight(Node *a, int weight) {
		Tree::expose(a);
		a->weight = weight;
		a->pathAndTreeUpdate();
	}

	static long long getPathWeightSum(Node *a, Node *b) {
		Node *orgRoot = Tree::exposePath(a, b);
		long long res = b->pathWeightSum;
		Tree::evert(orgRoot);
		return res;
	}

	static long long getTreeWeightSum(Node *a) {
		Tree::expose(a);
		return a->treeWeightSum;
	}

	static ll getMaxDistance(Node *a) {
		Node *orgRoot = Tree::getTreeRoot(a);
		Tree::evert(a);
		ll res = Node::getNodeMaxDistLR(a, false) - a->weight;
		Tree::evert(orgRoot);
		return res;
	}

};

int main() {
	int Q;
	while(~scanf("%d", &Q)) {
		vector<Node> nodes(Q*2 + 1);
		nodes[0] = Node();
		int nNodes = 1;
		rep(ii, Q) {
			int T, A, C;
			scanf("%d%d%d", &T, &A, &C);
			if(T == 1) {
				Node *a = &nodes[A * 2];
				Node *e = &nodes[nNodes ++];
				Node *v = &nodes[nNodes ++];
				NodeOps::setWeight(e, C);
				Tree::link(a, e);
				Tree::link(e, v);
			}else if(T == 2) {
				Node *e = &nodes[A * 2 - 1];
//				cerr << NodeOps::getWeight(e) << " -> " << C << endl;
				NodeOps::setWeight(e, C);
			}else if(T == 3) {
				Node *a = &nodes[A * 2];
				ll ans = NodeOps::getMaxDistance(a);
				printf("%lld\n", ans);
			}else {
				abort();
			}
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:557:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &T, &A, &C);
                               ^

Judge Result