Pagini recente » Cod sursa (job #2951950) | Cod sursa (job #1810328) | Cod sursa (job #2850279) | Cod sursa (job #1502460) | Cod sursa (job #796214)
Cod sursa(job #796214)
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
const int Nmax = 100010;
const int Sqv = 320;
const int Smax = 1000010;
vector<int> Leg[Nmax];
int N,M,Act,Sec,Nbr;
int Begin[Nmax];
int Norm[Nmax];
int End[Nmax];
int Dad[Nmax];
int A[Nmax];
int B[Sqv];
bitset<Sqv> P[Smax];
ifstream F("arbore.in");
ofstream G("arbore.out");
void Get(int Nod)
{
++Act;
Begin[Nod]=Act;
Norm[Act]=Nod;
for (vector<int>::iterator it=Leg[Nod].begin();it!=Leg[Nod].end();++it)
if ( *it != Dad[Nod] )
Get( *it );
End[Nod]=Act;
}
void Update(int st,int dr,int val)
{
for (int i=1;i<=Nbr;++i)
{
int l = (i-1)*Sec+1;
int r = min(i*Sec,N);
if ( l >= st && r <= dr )
B[i] += val;
else
if ( l <= st && r >= dr )
{
for ( int j=st;j<=dr;++j )
{
A[j] += val;
P[i][A[j]] = 1;
}
}
else
if ( l <= st && r <= dr )
{
for ( int j=st;j<=r;++j )
{
A[j] += val;
P[i][A[j]] = 1;
}
}
else if ( l >= st && r >= dr )
{
for ( int j=l;j<=dr;++j )
{
A[j] += val;
P[i][A[j]] = 1;
}
}
}
}
void Query( int Sum )
{
for (int i=1;i<=Nbr;++i)
if ( Sum-B[i]>=0 )
if ( P[i][Sum-B[i]] || Sum-B[i] == 0 )
{
for (int j=1;j<=Sec;++j)
if ( A[(i-1)*Sec+j]+B[i] == Sum )
{
G<<Norm[(i-1)*Sec+j]<<'\n';
return;
}
}
G<<-1<<'\n';
}
int main()
{
F>>N>>M;
for (int i=1,x,y;i<N;++i)
{
F>>x>>y;
Leg[x].push_back( y );
Leg[y].push_back( x );
Dad[ y ]= x;
}
Get( 1 );
Sec = (int) sqrt(double(N));
Nbr = N/Sec + ( (N/Sec) *Sec < N );
while ( M-- )
{
int type,a,b;
F>>type;
if ( type == 1 )
{
F>>a>>b;
Update( Begin[a] , End[a] , b );
}
else
{
F>>a;
Query( a );
}
}
}