Pagini recente » Cod sursa (job #804355) | Cod sursa (job #637350) | Cod sursa (job #2345957) | Cod sursa (job #2197039) | Cod sursa (job #998969)
Cod sursa(job #998969)
#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;
}