Pagini recente » Cod sursa (job #1408433) | Cod sursa (job #3342277) | Cod sursa (job #3301449) | Cod sursa (job #3305701) | Cod sursa (job #3334741)
#include <bits/stdc++.h>
using namespace std;
const int BUCKETS=320,Nmax=1e5+5;
int v[Nmax],vstart[Nmax],vend[Nmax],normm[Nmax],vlazy[BUCKETS];
bool viz[Nmax];
vector<int> tree[Nmax];
unordered_map<int,int> fr[BUCKETS];
int timer;
void dfs(int node) {
vstart[node]=++timer;
normm[timer]=node;
viz[node]=1;
for (auto x:tree[node]) {
if (!viz[x]) dfs(x);
}
vend[node]=timer;
}
void add(int poz, int nrb, int sum) {
fr[nrb][v[poz]]--;
if (!fr[nrb][v[poz]]) fr[nrb].erase(v[poz]);
v[poz]+=sum;
fr[nrb][v[poz]]++;
}
int main() {
ifstream fin("arbore.in");
ofstream fout("arbore.out");
int n,m;
fin>>n>>m;
for (int i=1; i<=n-1; ++i) {
int x,y;
fin>>x>>y;
tree[x]. push_back(y);
tree[y].push_back(x);
}
dfs(1);
int b=sqrt(n);
for (int i=1,nrb=0; i<=n; i+=b,++nrb) {
int end=min(i+b,n+1);
fr[nrb][0]=(end-i);
}
while (m--) {
int type;
fin>>type;
if (type==1) {
int p,s;
fin>>p>>s;
int st=vstart[p],dr=vend[p];
int x=(st-1)/b,y=(dr-1)/b;
if (x==y) {
for (int j=st; j<=dr; ++j) {
add(j,x,s);
}
} else {
int c=min((x+1)*b+1,n+1);
for (int j=st; j<c; ++j) {
add(j,x,s);
}
for (int j=dr; j>=y*b+1; --j) {
add(j,y,s);
}
for (int k=x+1; k<y; ++k) {
vlazy[k]+=s;
}
}
}
else {
int s;
fin>>s;
int nrb=(n+b-1)/b;
int ans=-1;
for (int k=0,i=1; k<nrb && ans==-1; ++k,i+=b) {
if (fr[k]. count(s-vlazy[k])) {
for (int j=i; j<=min(i+b-1,n); ++j) {
if (v[j]+vlazy[k]==s) {
ans=normm[j];
break;
}
}
}
}
fout<<ans<<'\n';
}
}
fin.close();
fout.close();
return 0;
}