Cod sursa(job #3370512)

Utilizator batasAndrei Batis batas Data 26 octombrie 2026 14:45:11
Problema Arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;

ifstream fin("arbore.in");
ofstream fout("arbore.out");

const int MAX_N = 1e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int pos[MAX_N], tin[MAX_N], tout[MAX_N], timer;
VI seg, lazy, minV, maxV;
VVI adj;

void ReadInput();
void Solve();
void DFS(int node, int fa);
void Update(int node, int start, int fin, int l, int r, int val);
int Query(int node, int start, int fin, int sum);
void PushDown(int node, int start, int fin);

int main()
{
    ReadInput();
    DFS(1, 0);
    Solve();

    return 0;
}

void Solve()
{
    seg = lazy = minV = maxV = VI(4 * timer + 5, 0);

    int type, node, sum;
    while (m--)
    {
        fin >> type;

        if (type == 1)
        {
            fin >> node >> sum;

            Update(1, 1, timer, tin[node], tout[node], sum);
        }
        else
        {
            fin >> sum;
            fout << Query(1, 1, n, sum) << '\n';
        }
    }
}

int Query(int node, int start, int fin, int sum)
{
	PushDown(node, start, fin);

	if (start == fin)
	{
		if (seg[node] == sum)
			return pos[start];
		return -1;
	}
	
	if (minV[node] > sum || maxV[node] < sum)
		return -1;
		
	int mid = (start + fin) / 2;
	int res1, res2;
	res1 = Query(2 * node, start, mid, sum);
	
	if (res1 != -1)
		return res1;
	
	res2 = Query(2 * node + 1, mid + 1, fin, sum);
	return res2;
}

void Update(int node, int start, int fin, int l, int r, int val)
{
    PushDown(node, start, fin);

    if (r < start || l > fin)
        return;

    if (l <= start && r >= fin)
    {
        lazy[node] += val;
        PushDown(node, start, fin);
        return;
    }

    int mid = (start + fin) / 2;
    Update(2 * node, start, mid, l, r, val);
    Update(2 * node + 1, mid + 1, fin, l, r, val);

    seg[node] = seg[2 * node] + seg[2 * node + 1];
    minV[node] = min(minV[2 * node], minV[2 * node + 1]);
    maxV[node] = max(maxV[2 * node], maxV[2 * node + 1]);
}

void PushDown(int node, int start, int fin)
{
    if (lazy[node] != 0)
    {
        seg[node] += (fin - start + 1) * lazy[node];
		minV[node] += lazy[node];
		maxV[node] += lazy[node];

        if (start != fin)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }

        lazy[node] = 0;
    }
}

void DFS(int node, int fa)
{
    tin[node] = ++timer;
    pos[timer] = node;

    for (int nbr : adj[node])
        if (nbr != fa)
            DFS(nbr, node);

    tout[node] = timer;
}

void ReadInput()
{
    fin >> n >> m;

    adj = VVI(n + 1);

    int u, v;
    for (int i = 1; i < n; ++i)
    {
        fin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}