# Cod sursa(job #1455590)

Utilizator Data 28 iunie 2015 16:02:34 Heavy Path Decomposition 100 cpp done Arhiva educationala 2.71 kb
``````#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int A[100002];
int W[100002], niv[100002], T[100002];
vector<int> V[100002];
int where[100002], wnod[100002], what[100002], L1[100002], L2[100002];
int ARB[4 * 100002], A1, A2, Av, Ap;

void setall(int nod, int i1, int i2)
{
if (i1 == i2)
{
ARB[nod] = A[wnod[i1]];
return;
}

int mid = (i1 + i2) / 2;
setall(nod * 2, i1, mid);
setall(nod * 2 + 1, mid + 1, i2);

ARB[nod] = max(ARB[nod * 2], ARB[nod * 2 + 1]);
}
void update(int nod, int i1, int i2)
{
if (i1 == i2)
{
ARB[nod] = A[wnod[i1]];
return;
}

int mid = (i1 + i2) / 2;
if (Ap <= mid) update(nod * 2, i1, mid);
else           update(nod * 2 + 1, mid + 1, i2);

ARB[nod] = max(ARB[nod * 2], ARB[nod * 2 + 1]);
}
void query(int nod, int i1, int i2)
{
if (A1 <= i1 && i2 <= A2)
{
Av = max(Av, ARB[nod]);
return;
}

int mid = (i1 + i2) / 2;
if (A1 <= mid) query(nod * 2, i1, mid);
if (A2 > mid)  query(nod * 2 + 1, mid + 1, i2);
}

void preDfs(int x)
{
W[x] = 1;
for (auto nod : V[x])
if (!W[nod])
{
T[nod] = x;
niv[nod] = niv[x] + 1;
preDfs(nod);
W[x] += W[nod];
}
}
void Dfs(int x)
{
bool any = false;
for (auto nod : V[x])
if (nod != T[x])
{
if (2 * W[nod] > W[x] - 1)
{
any = true;
where[nod] = x;
}
Dfs(nod);
}

if (!any)
{
++what[0];

int nod = x;
while (true)
{
bool endnow = (where[nod] == 0);

where[nod] = ++where[0];
wnod[where[0]] = nod;
what[nod] = what[0];
nod = T[nod];

if (L1[what[0]] == 0)
L1[what[0]] = wnod[where[0]];
L2[what[0]] = wnod[where[0]];

if (endnow) break;
}
}
}

int getmax(int i1, int i2)
{
if (what[i1] == what[i2])
{
if (where[i1] > where[i2]) swap(i1, i2);
A1 = where[i1], A2 = where[i2], Av = 0;
query(1, 1, N);

return Av;
}
else if (niv[L2[what[i1]]] < niv[L2[what[i2]]])
{
A1 = where[i2], A2 = where[L2[what[i2]]], Av = 0;
query(1, 1, N);

int aux = Av;
return max(aux, getmax(i1, T[L2[what[i2]]]));
}
else
{
A1 = where[i1], A2 = where[L2[what[i1]]], Av = 0;
query(1, 1, N);

int aux = Av;
return max(aux, getmax(T[L2[what[i1]]], i2));
}
}

int main()
{
ifstream fin("heavypath.in");
ofstream fout("heavypath.out");

fin >> N >> M;
for (int i = 1; i <= N; ++i)
fin >> A[i];
for (int i = 1, nod1, nod2; i <= N - 1; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
V[nod2].push_back(nod1);
}

niv[1] = 1;
preDfs(1);
Dfs(1);

setall(1, 1, N);

for (int i = 1, type, v1, v2; i <= M; ++i)
{
fin >> type >> v1 >> v2;
if (type == 0)
{
A[v1] = v2;
Ap = where[v1];
update(1, 1, N);
}
else
fout << getmax(v1, v2) << '\n';
}

fin.close();
fout.close();
}
``````