Submission #783372

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

const int N = 100000;
int n;
vector<set<int>> e;
vector<pair<pi, int>> es;

int sz, id[N], to[N];
set<pi> s[N]; //(cost, id)
/*
int rec_sz(int c, int p){
	int res = 1;
	for(int i : e[c]){
		int s = es[i].first.first, t = es[i].first.second;
		if(c == t) swap(s, t);
		if(t == p) continue;
		res += rec_sz(t, c);
	}
	return res;
}
*/
void rec(set<pi> &s1, set<pi> &s2, int c, int p){
	for(int i : e[c]){
		int s = es[i].first.first, t = es[i].first.second;
		if(t == c) swap(s, t);
		if(t == p) continue;
		s2.insert(mp(es[i].second, i));
		s1.erase(mp(es[i].second, i));
		to[i] = sz;
		rec(s1, s2, t, c);
	}
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	cin >> n;
	e.resize(n);
	rep(i, n - 1){
		int a, b, c; cin >> a >> b >> c; a--; b--;
		e[a].insert(i);
		e[b].insert(i);
		es.pb(mp(mp(a, b), c));
		s[0].insert(mp(c, i));
	}
	sz++;
	
	int q; cin >> q;
	vi avis(n), bvis(n);
	
	while(q--){
		int t, idx, d; cin >> t >> idx; idx--;
		if(t == 1){
			cin >> d;
			if(es[idx].second == -inf) continue;
			s[to[idx]].erase(mp(es[idx].second, idx)); es[idx].second += d;
			s[to[idx]].insert(mp(es[idx].second, idx));
			continue;
		}
		//rep(i, es.size()) dbg(es[i]); cerr<<endl;
		if(es[idx].second == -inf){ puts("-1"); continue; }
		
		pi mn = *s[to[idx]].begin();
		idx = mn.second;
		printf("%d\n", idx + 1);
		
		int a = es[idx].first.first, b = es[idx].first.second;
		e[a].erase(idx);
		e[b].erase(idx);
		//int sa = rec_sz(a, a), sb = rec_sz(b, b);
		vi av(1, a), bv(1, b);
		int ap = a, bp = b, asml = 1, af = 0, bf = 0;
		auto ae = e[ap].begin(), be = e[bp].begin();
		
		queue<int> qa, qb;
		qa.push(a); qb.push(b);
		
		while(1){
			BACKA:
			if(ae == e[ap].end()){
				af = 1;
				if(qa.empty()) break;
				ap = qa.front(); qa.pop();
			}
			{
				if(af) ae = e[ap].begin(), af = 0; if(ae == e[ap].end()) goto BACKA;
				int s = es[*ae].first.first, t = es[*ae].first.second;
				if(t == a) swap(s, t); ++ae;
				if(avis[t]) goto BACKA;
				qa.push(t); avis[t] = 1; av.pb(t);
			}
			BACKB:
			if(be == e[bp].end()){
				bf = 1;
				if(qb.empty()){ asml = 0; break; }
				bp = qb.front(); qb.pop();
			}
			{
				if(bf) be = e[bp].begin(), bf = 0; if(be == e[bp].end()) goto BACKB;
				int s = es[*be].first.first, t = es[*be].first.second;
				if(t == b) swap(s, t); ++be;
				if(bvis[t]) goto BACKB;
				qb.push(t); bvis[t] = 1; bv.pb(t);
			}
		}
		for(int i : av) avis[i] = 0;
		for(int i : bv) bvis[i] = 0;
		
		if(!asml) swap(a, b);
		
		s[to[idx]].erase(mp(es[idx].second, idx));
		es[idx].second = -inf;
		rec(s[to[idx]], s[sz], a, a);
		sz++;
	}
	return 0;
}

Submission Info

Judge Result