Pagini recente » Borderou de evaluare (job #2238163) | Cod sursa (job #2734777)
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("arbore.in");
ofstream fout("arbore.out");
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
}fin ("arbore.in");
int N, M;
vector <int> v[100005];
struct Rad
{
int add;
unordered_map <int, int> fvv;
};
Rad fv[405];
int vals[100005];
int sz[100005], label[100005], k, rlabel[100005], lbuck;
void dfs(int node, int dad)
{
sz[node]++;
label[node] = ++k;
rlabel[k] = node;
for(int i = 0; i < v[node].size(); i++)
if(v[node][i] != dad)
{
dfs(v[node][i], node);
sz[node] += sz[v[node][i]];
}
}
void update(int st, int dr, int val)
{
int buck_st, buck_dr;
buck_st = (st - 1) / lbuck + 1;
buck_dr = (dr - 1) / lbuck + 1;
if(buck_st == buck_dr)
{
for(int i = st; i <= dr; i++)
{
fv[buck_st].fvv[vals[i]]--;
vals[i] += val;
fv[buck_st].fvv[vals[i]]++;
}
return;
}
for(int i = buck_st + 1; i <= buck_dr - 1; i++)
fv[i].add += val;
for(int i = st; i <= min(((st - 1) / lbuck + 1) * lbuck, N); i++)
{
fv[buck_st].fvv[vals[i]]--;
vals[i] += val;
fv[buck_st].fvv[vals[i]]++;
}
for(int i = (buck_dr - 1) * lbuck + 1; i <= dr; i++)
{
fv[buck_dr].fvv[vals[i]]--;
vals[i] += val;
fv[buck_dr].fvv[vals[i]]++;
}
}
int ask(int val)
{
for(int i = 1; i <= (N - 1) / lbuck + 1; i++)
{
if(fv[i].fvv[val - fv[i].add] != 0)
{
for(int j = (i - 1) * lbuck + 1; j <= i * lbuck; j++)
if(vals[j] + fv[i].add == val)
return rlabel[j];
}
}
return -1;
}
int main()
{
fin >> N >> M;
lbuck = sqrtl(N);
for(int i = 1; i <= N - 1; i++)
{
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
for(int i = 1; i <= N; i++)
{
int buck_i = (i - 1) / lbuck + 1;
fv[buck_i].fvv[0]++;
}
for(int i = 1; i <= M; i++)
{
int t;
fin >> t;
if(t == 1)
{
int x, y;
fin >> x >> y;
update(label[x], label[x] + sz[x] - 1, y);
}
else
{
int x;
fin >> x;
fout << ask(x) << '\n';
}
}
return 0;
}