Pagini recente » Cod sursa (job #1417397) | Cod sursa (job #3133808) | Cod sursa (job #908808) | Cod sursa (job #2101352) | Cod sursa (job #1481495)
#include<bits/stdc++.h>
#define Lim 500000
#define Next (++pos==Lim)?(fin.read(Buffer,Lim),pos = 0):0
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
const int MODULO=10007;
const int NMAX=100005;
const int SQMAX=405;
int n,m,len,sq,eu[NMAX],start[NMAX],stop[NMAX],which[NMAX],pos;
int add[SQMAX],a[NMAX];
vector<int>v[NMAX];
unordered_map<int,int>M[SQMAX];
char Buffer[Lim];
inline void Read(int &x)
{
bool ok=0;
while(Buffer[pos]<'0' || '9'<Buffer[pos])
{
if (Buffer[pos]=='-') ok=1;
Next;
}
x = 0;
while('0'<=Buffer[pos] && Buffer[pos]<='9')
{
x = x*10 +Buffer[pos]-'0';
Next;
}
if (ok==1) x=-x;
}
inline void Dfs(int x,const int f)
{
eu[++len]=x;
start[x]=len;
for (vector<int>::iterator it=v[x].begin();it!=v[x].end();it++)
if ((*it)!=f)
Dfs(*it,x);
stop[x]=len;
}
inline void Solve(int x,int y,int who,int val)
{
int i,st,dr;
M[who].clear();
for (i=x;i<=y;i++) a[i]+=val;
dr=min(n,who*sq);st=(who-1)*sq+1;
for (i=st;i<=dr;i++)
M[who][a[i]]=eu[i];
}
int main()
{
int i,j,l,x,y,s,op,aux,poz;
fin.read(Buffer,Lim);
Read(n);Read(m);sq=sqrt(n);
for (i=1;i<n;i++)
{
Read(x);Read(y);
v[x].push_back(y);
v[y].push_back(x);
}
Dfs(1,0);
for (i=1;i<=n;i++)
{
which[i]=(i/sq)+1;
if (i%sq==0) which[i]--;
if (which[i]!=which[i-1]) M[which[i]][0]=eu[i];
}
for (l=1;l<=m;l++)
{
Read(op);
if (op==1)
{
Read(x);Read(s);
i=start[x];y=which[i];
if (i%sq!=1)
{
Solve(i,min(which[i]*sq,stop[x]),which[i],s);
i=which[i]*sq+1;
}
while ((i+sq-1)<=stop[x]) {add[which[i]]+=s;i+=sq;}
if (i<=stop[x]) Solve(i,stop[x],which[i],s);
}
if (op==2)
{
Read(s);
aux=0;poz=-1;
for (i=1;i<=n && poz>=0;i+=sq)
{
aux++;
if (M[aux].find(s-add[aux])!=M[aux].end())
poz=M[aux][s-add[aux]];
}
fout<<poz<<"\n";
}
}
return 0;
}