Pagini recente » Cod sursa (job #1118510) | Cod sursa (job #2659231) | Cod sursa (job #2411792) | Cod sursa (job #1790393) | Cod sursa (job #1481515)
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#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 NMAX=100005;
const int SQMAX=355;
int n,m,len,sq,eu[NMAX],start[NMAX],stop[NMAX],which[NMAX],pos;
int add[SQMAX],a[NMAX];
vector<int>v[NMAX];
bitset<1000005>H[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;
dr=min(n,who*sq);st=(who-1)*sq+1;
for (i=st;i<=dr;i++) H[who][a[i]]=0;
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++) H[who][a[i]]=1;
}
int main()
{
int i,j,l,x,y,s,op,aux,poz,baux;
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]) H[which[i]][0]=1;
}
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 ((s-add[aux])>=0 && H[aux][s-add[aux]]==1)
{
baux=aux*sq;
for (j=i;j<=baux;j++)
if ((a[j]+add[aux])==s)
poz=eu[j];
}
}
fout<<poz<<"\n";
}
}
return 0;
}