Pagini recente » Cod sursa (job #1642361) | Cod sursa (job #61408) | Cod sursa (job #2979030) | Cod sursa (job #134542) | Cod sursa (job #915030)
Cod sursa(job #915030)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int i,j,n,m,x,y,tip,p,s,sum[100001],s1[1000001],cr[1000001],start;
int tata[1000001],niv[1000001];
bool viz[1000001];
vector<int> a[100001];
void init()
{
for(int i=1;i<=n;++i)
viz[i]=0;
}
void df(int x)
{
int i;
viz[x]=1;
for(i=0;i<a[x].size();++i)
if(!viz[a[x][i]])
{
niv[a[x][i]]=niv[x]+1;
tata[a[x][i]]=x;
df(a[x][i]);
}
}
void det(int x)
{
int i;
viz[x]=1;
for(i=0;i<a[x].size();++i)
if(!viz[a[x][i]]&&niv[a[x][i]]>niv[x])
{
sum[a[x][i]]+=sum[x];
det(a[x][i]);
}
s1[sum[x]]=x;
}
int main()
{
ifstream f("arbore.in");
ofstream g("arbore.out");
f>>n>>m;
for(i=1;i<n;++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
df(1);
start=0;
niv[0]=10000000;
for(i=1;i<=m;++i)
{
f>>tip;
if(tip==1)
{
f>>p>>s;
if(niv[p]<niv[start])
start=p;
else
if(niv[p]==niv[start])
start=tata[p];
sum[p]+=s;
}
else
{
init();
f>>s;
det(start);
if(s1[s])
g<<s1[s]<<"\n";
else
g<<"-1"<<"\n";
}
}
return 0;
}