Cod sursa(job #2622872)

Utilizator infinite_iqBesher Islambouley infinite_iq Data 1 iunie 2020 23:52:08
Problema Arbore Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.27 kb
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
//#define mp make_pair
#define mid (l+r)/2
#define Le Node * 2 
#define Ri Node * 2 + 1 
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef pair<double,ll>pdi;
const ll inf=1e18;
const ll Mod=1e9+7;
const ld pai=acos(-1);
int n , q ;
vi a [sqr] , v [100009] ;
int sum [sqr] ;
unordered_map < int , vi > mp [sqr] ;
//
int ord [100009] , st [100009] , en [100009] , timer ;
void dfs ( int node , int p ) {
	ord [timer] = node ; 
	st [node] = timer ++ ;
	for ( auto u : v [node] ) {
		if ( u == p ) C ;
		dfs ( u , node ) ;
	}
	en [node] = timer - 1 ; 
}
int main () {
	freopen("arbore.in", "r", stdin);
	freopen("arbore.out", "w", stdout);
	cin >> n >> q ;
	for ( int i = 0 ; i < n ; i ++ ) {
		a [i/sqr] .pb ( 0 ) ;
		mp[i/sqr][0] .pb ( i ) ;
	}
	for ( int i = 0 ; i < n - 1 ; i ++ ) {
		int a , b ;
		scanf("%d%d",&a,&b) ;
		a -- , b -- ;
		v [a] .pb ( b ) ;
		v [b] .pb ( a ) ;
	}
	dfs ( 0 , 0 ) ;
	while ( q -- ) {
		int t ;
		cin >> t ;
		if ( t == 1 ) {
			int node , x , l , r ;
			scanf("%d%d",&node,&x) , node -- ;
			l = st [node] , r = en [node] ;
			if ( l / sqr == r / sqr ) {
				int id = l / sqr ;
				for ( int i = l % sqr ; i <= r % sqr ; i ++ ) {
					a [id][i] += x ;
					mp[id][a[id][i]] .pb (i) ;
				} 
				C ;
			}
			int id = l /sqr ;
			for ( int i = l%sqr ; i%sqr != 0 ; i ++ ) {
				l ++ ;
				a [id][i] += x ;
				mp[id][a[id][i]] .pb (i) ;
			}
			id = r / sqr ;
			for ( int i = r % sqr ; i%sqr != sqr-1 ; i -- ) {
				r -- ;
				a [id][i] += x ;
				mp[id][a[id][i]] .pb (i) ; 
			}
			while ( l < r ) {
				sum [l/sqr] += x ;
				l += sqr ;
			}
		}
		else {
			int x , l , r , z = 0 ;
			scanf("%d",&x) ;
			l = 0 , r = n-1 ;
			if ( l/sqr == r/sqr ) {
				int id = l/sqr ;
				for ( int i = l%sqr ; i <= r%sqr ; i ++ ) {
					if ( a [id][i] + sum [id] == x ) {
						printf("%d\n",ord [id*sqr+i] + 1) ;
						z = 1 ;
						break ;
					}
				}
				if (!z) puts("-1") ;
				C ;
			}
                        int id = r / sqr ;
                        for ( int i = r % sqr ; i%sqr != sqr-1 ; i -- ) {
                                r -- ;
				if ( a [id][i] + sum [id] == x ) {
                                        printf("%d\n",ord [id*sqr+i] + 1 ) ;
                                        z = 1 ;
                                        break ;
                                }
                        }
			if (z) C ;
			while ( l < r ) {
				int id = l / sqr ;
				int goal = x - sum [id] ;
			       	if ( goal >= 0 ) {	
					while ( mp [id][goal] .size () ) {
						int who = mp[id][goal].back() ;
						if ( a [id][who] == goal ) {
							printf("%d\n",ord [id*sqr+who] + 1 );
							z = 1 ;
							break ;
						}
					}
					if (z) break ; 
				}
				l += sqr ;
			}
			if (!z) puts ("-1") ; 
		}
	}
}