Cod sursa(job #998969)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 18 septembrie 2013 20:52:37
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb

#include <cstdio>
#include <vector>
#include <bitset>
#include <utility>
#include <cmath>

typedef std::pair<int,int> Bucket;

const int MAX_N(100005);
const int MAX_BUCKET(317);
const int MAX_VALUE(1000005);

int n, m, Size;
std::vector<int> Graph [MAX_N];
std::bitset<MAX_VALUE> Mark [MAX_BUCKET];
Bucket v [MAX_BUCKET];
int Tree [MAX_N], Pos;
std::pair<int,int> Index [MAX_N];
int Add [MAX_BUCKET];
int Value [MAX_N];

inline void Read (void)
{
	std::scanf("%d %d",&n,&m);
	for (int i(1), x, y ; i < n ; ++i)
	{
		std::scanf("%d %d",&x,&y);
		Graph[x].push_back(y);
		Graph[y].push_back(x);
	}
}

void TreeDecomposition (int node, int parent)
{
	Tree[Pos] = node;
	Index[node].first = Pos;
	++Pos;
	for (auto it : Graph[node])
		if (it != parent)
			TreeDecomposition(it,node);
	Index[node].second = Pos - 1;
}

inline void Build (void)
{
	int root(std::sqrt(n));
	int i(0), j(root - 1);
	while (true)
	{
		++Size;
		v[Size].first = i;
		v[Size].second = j;
		Mark[Size][0] = true;
		if (j == n - 1)
			break;
		i = j + 1;
		j = std::min(j + root,n - 1);
	}
}

inline void Update (int left, int right, int value)
{
	for (int i(1) ; i <= Size && v[i].first <= right ; ++i)
	{
		if (left <= v[i].first && v[i].second <= right)
			Add[i] += value;
		else if (!(left > v[i].second || right < v[i].first))
		{
			for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
			{
				Mark[i][Value[Tree[j]]] = false;
				Value[Tree[j]] += Add[i] + (left <= j && j <= right ? value : 0);
			}
			Add[i] = 0;
			for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
				Mark[i][Value[Tree[j]]] = true;
		}
	}
}

inline int Query (int value)
{
	for (int i(1) ; i <= Size ; ++i)
		if (Add[i] <= value && Mark[i][value - Add[i]])
		{
			for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
				if (Value[Tree[j]] + Add[i] == value)
					return Tree[j];
		}
	return -1;
}

int main (void)
{
	std::freopen("arbore.in","r",stdin);
	std::freopen("arbore.out","w",stdout);
	Read();
	TreeDecomposition(1,1);
	Build();
	int t, x, y;
	while (m)
	{
		std::scanf("%d",&t);
		if (t == 2)
		{
			std::scanf("%d",&x);
			std::printf("%d\n",Query(x));
		}
		else
		{
			std::scanf("%d %d",&x,&y);
			Update(Index[x].first,Index[x].second,y);
		}
		--m;
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}