Pagini recente » Cod sursa (job #2651957) | Cod sursa (job #3228710) | Cod sursa (job #277608) | Cod sursa (job #1846682) | Cod sursa (job #915135)
Cod sursa(job #915135)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ofstream g("arbore.out");
int i,j,n,m,x,y,tip,p,s,sum[1000001],s1[1000001],ok,nr=0;
int ic[100001],sf[100001];
bool viz[1000001];
vector<int> a[100001];
void df(int x)
{
int i;
viz[x]=1;
++nr;
ic[x]=sf[x]=nr;
for(i=0;i<a[x].size();++i)
if(!viz[a[x][i]])
{
df(a[x][i]);
sf[x]=nr;
}
}
int main()
{
ifstream f("arbore.in");
f>>n>>m;
for(i=1;i<n;++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
df(1);
for(i=1;i<=m;++i)
{
f>>tip;
if(tip==1)
{
f>>p>>s;
sum[ic[p]]+=s;
sum[sf[p]+1]-=s;
}
else
{
f>>s;
for(j=1;j<=n;++j)
s1[j]=s1[j-1]+sum[j];
ok=0;
for(j=1;j<=n&&!ok;++j)
if(s1[ic[j]]==s)
g<<j<<"\n",ok=1;
if(!ok)
g<<"-1"<<"\n";
}
}
return 0;
}