Pagini recente » Cod sursa (job #2600580) | Cod sursa (job #291836) | Cod sursa (job #1266168) | Cod sursa (job #2628196) | Cod sursa (job #2622872)
#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") ;
}
}
}