Pagini recente » Cod sursa (job #2980740) | Cod sursa (job #311029) | Cod sursa (job #2374619) | Cod sursa (job #1693529) | Cod sursa (job #2072911)
#include <bits/stdc++.h>
using namespace std;
FILE *fin = fopen( "arbore.in", "r" );
FILE *fout= fopen( "arbore.out","w" );
const int BUF = (1<<17);
const int maxv = 1e6 + 1;
const int maxn = 1e5 + 5;
const int Sqrt = 128;
const int buck = 1000;
char buf[BUF], buf2[BUF];
int pos = BUF, pos2;
inline char getChar() {
if (pos == BUF)
pos = 0, fread( buf, 1, BUF, fin );
return buf[ pos++ ];
}
inline int getInt() {
int nr = 0;
char c = getChar();
while (!isdigit(c))
c = getChar();
while (isdigit(c)) {
nr = nr*10 + c-'0';
c = getChar();
}
return nr;
}
inline void writeChar( char c ) {
buf2[ pos2++ ] = c;
if (pos2 == BUF)
pos2 = 0, fwrite( buf2, 1, BUF, fout );
}
inline void writeInt( int nr ) {
char s[ 15 ];
int sg = 1, top = 0;
if (nr < 0)
sg = -1, nr *= -1;
while (nr) {
s[ top++ ] = nr%10 + '0';
nr /= 10;
}
if (sg == -1)
s[ top++ ] = '-';
while (top) {
top--;
writeChar( s[ top ] );
}
}
vector < int > G[maxn];
pair < int, int > Ends[maxn];
unordered_set < int > val[buck];
int n, m, k, v[maxn], values[maxn], where[maxn], lazy[buck];
void dfs( int node, int dad ) {
v[ ++k ] = node;
Ends[ node ].first = k;
for (int son: G[ node ])
if (son != dad)
dfs( son, node );
Ends[ node ].second = k;
}
inline void update( int x, int y, int value ) {
if (where[ x ] == where[ y ]) {
for (int i = x; i <= y; i++)
values[ i ] += value;
val[ where[ x ] ].clear();
for (int i = (where[ x ] - 1) * Sqrt + 1; i <= where[ x ] * Sqrt; i++)
val[ where[ x ] ].insert( values[ i ] );
return;
}
for (int i = where[ x-1 ] + 1; i < where[ y+1 ]; i++)
lazy[ i ] += value;
pair <int, int> left, right;
if (where[ x-1 ] == where[ x ]) {
left = { x, min( y, where[ x ] * Sqrt ) };
for (int i = left.first; i <= left.second; i++)
values[ i ] += value;
val[ where[ x ] ].clear();
for (int i = left.first; i <= left.second; i++)
val[ where[ x ] ].insert( values[ i ] );
}
if (where[ y ] == where[ y+1 ]) {
right = { max( (where[ y ] - 1) * Sqrt + 1, x ), y };
for (int i = right.first; i <= right.second; i++)
values[ i ] += value;
val[ where[ y ] ].clear();
for (int i = right.first; i <= right.second; i++)
val[ where[ y ] ].insert( values[ i ] );
}
}
inline int searchBucket( int idx, int sum ) {
for (int i = (idx - 1) * Sqrt + 1; i <= idx * Sqrt; i++)
if (values[ i ] == sum)
return v[ i ];
return -1;
}
inline int query( int sum ) {
for (int i = 1; (i-1) * Sqrt + 1 <= n; i++)
if (val[ i ].find( sum - lazy[ i ] ) != val[ i ].end())
return searchBucket( i, sum - lazy[ i ] );
return -1;
}
int main()
{
int op, x, y;
n = getInt();
m = getInt();
for (int i = 1; i < n; i++) {
x = getInt();
y = getInt();
G[ x ].push_back( y );
G[ y ].push_back( x );
}
for (int i = 1; (i-1) * Sqrt + 1 <= n + 1; i++) {
where[ (i-1) * Sqrt + 1 ] = i;
val[ i ].insert( 0 );
}
for (int i = 1; i <= n + 1; i++)
if (!where[ i ])
where[ i ] = where[ i-1 ];
dfs( 1, 0 );
for (int i = 1; i <= m; i++) {
op = getInt();
if (op == 1) {
x = getInt();
y = getInt();
update( Ends[ x ].first, Ends[ x ].second, y );
}
else {
x = getInt();
writeInt( query( x ) );
writeChar( '\n' );
}
}
if (pos2)
fwrite( buf2, 1, pos2, fout );
return 0;
}