Pagini recente » Cod sursa (job #2074524) | Cod sursa (job #2093886) | Cod sursa (job #940939) | Cod sursa (job #1520369) | Cod sursa (job #3240848)
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
ifstream cin("arbore.in");
ofstream cout("arbore.out");
int n,m,ce,arbore[200005],k,first[100005],last[100005],mars[200005];
bool viz[100005];
vector<int>l[100005];
void dfs(int nod)
{
viz[nod]=1;
arbore[++k]=nod;
first[nod]=k;
for(int i=0; i<l[nod].size(); i++)
{
int vecin=l[nod][i];
if(viz[vecin]==0)
dfs(vecin);
}
arbore[++k]=nod;
last[nod]=k;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n-1; i++)
{
int x,y;
cin>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
dfs(1);
/**for(int i=1;i<=k;i++)
cout<<arbore[i]<<" ";
cout<<'\n';**/
while(m--)
{
int ce;
cin>>ce;
if(ce==1)
{
int p,s;
cin>>p>>s;
mars[first[p]]+=s;
mars[last[p]+1]-=s;
}
else if(ce==2)
{
int sum;
cin>>sum;
int s=0,sol=-1,ok=1;
/**for(int i=1;i<=k;i++)
cout<<mars[i]<<" ";
cout<< " ";**/
for(int i=1; i<=k; i++)
{
s+=mars[i];
// cout<<s<<" ";
if(s==sum)
{
sol=arbore[i];
ok=0;
}
if(ok==0)
break;
}
cout<<sol<<'\n';
}
}
return 0;
}
///liniarizarea arborelui +mars