This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <cstdio> | |
#include <cassert> | |
#include <cstring> | |
#include <vector> | |
#include <valarray> | |
#include <array> | |
#include <queue> | |
#include <set> | |
#include <unordered_set> | |
#include <map> | |
#include <unordered_map> | |
#include <algorithm> | |
#include <cmath> | |
#include <complex> | |
#include <random> | |
using namespace std; | |
typedef long long ll; | |
typedef pair<int, int> P; | |
int dc = 0; | |
struct Tree { | |
typedef Tree* NP; | |
NP l, r; | |
struct Node { | |
Node(int sz = 0) : sz(sz) {} | |
int sz; | |
int d, sm, lz; | |
int lsm, rsm, ma, mv; | |
bool lzf; | |
} n; | |
Tree() {} | |
Tree(int sz, int hev[], int hevsm[]) : n(sz) { | |
if (sz == 1) return; | |
int sm = hevsm[sz] - hevsm[0]; | |
int md = lower_bound(hevsm, hevsm+sz-1, sm/2+hevsm[0]) - hevsm; | |
// int md = sz/2; | |
l = new Tree(md, hev, hevsm); | |
r = new Tree(sz - md, hev+md, hevsm+md); | |
} | |
void lzdata(int d) { | |
n.d = n.mv = d; | |
n.sm = n.sz*d; | |
n.lsm = n.rsm = n.ma = max(0, n.sm); | |
n.lz = d; | |
n.lzf = true; | |
} | |
void push() { | |
if (n.sz == 1) return; | |
if (n.lzf) { | |
l->lzdata(n.lz); | |
r->lzdata(n.lz); | |
n.lzf = false; | |
} | |
} | |
static Node merge(const Node &l, const Node &r) { | |
if (l.sz == 0) return r; | |
if (r.sz == 0) return l; | |
dc++; | |
Node res(l.sz + r.sz); | |
res.sm = l.sm+r.sm; | |
res.lsm = max(l.lsm, l.sm+r.lsm); | |
res.rsm = max(r.rsm, r.sm+l.rsm); | |
res.ma = max(max(l.ma, r.ma), l.rsm+r.lsm); | |
res.mv = max(l.mv, r.mv); | |
res.lzf = false; | |
return res; | |
} | |
static Node rev(Node u) { | |
swap(u.lsm, u.rsm); | |
return u; | |
} | |
void set(int k, int x) { | |
if (n.sz == 1) { | |
lzdata(x); | |
return; | |
} | |
push(); | |
if (k < l->n.sz) { | |
l->set(k, x); | |
} else { | |
r->set(k - l->n.sz, x); | |
} | |
n = merge(l->n, r->n); | |
} | |
void set(int a, int b, int x) { | |
if (b <= 0 || n.sz <= a) { | |
return; | |
} | |
push(); | |
if (a <= 0 && n.sz <= b) { | |
lzdata(x); | |
return; | |
} | |
l->set(a, b, x); | |
r->set(a - l->n.sz, b - l->n.sz, x); | |
n = merge(l->n, r->n); | |
} | |
Node get(int a, int b) { | |
if (b <= 0 || n.sz <= a) { | |
return Node(); | |
} | |
push(); | |
if (a <= 0 && n.sz <= b) { | |
return n; | |
} | |
return merge(l->get(a, b), r->get(a- l->n.sz, b- l->n.sz)); | |
} | |
}; | |
template <int N> | |
struct HLComp_Y { | |
vector<int> g[N]; | |
P n2l[N]; //node to line (line id - line pos) | |
int lc; | |
Tree *li[N]; //line data | |
P l2p[N]; //line to parent | |
int sz[N]; //node size | |
int buf[N]; // buffer of sz - sz[child] | |
int bufsm[N]; | |
int ldps[N]; // line dps | |
void add(int a, int b) { | |
g[a].push_back(b); | |
g[b].push_back(a); | |
} | |
void dfs_sz(int p, int b) { | |
sz[p] = 1; | |
for (int d: g[p]) { | |
if (d == b) continue; | |
dfs_sz(d, p); | |
sz[p] += sz[d]; | |
} | |
} | |
void dfs(int p, int b) { | |
if (g[p].size() == (b == -1 ? 0 : 1)) { | |
// make line | |
buf[n2l[p].second] = 1; | |
bufsm[n2l[p].second+1] = bufsm[n2l[p].second] + buf[n2l[p].second]; | |
li[n2l[p].first] = new Tree(n2l[p].second+1, buf, bufsm); | |
return; | |
} | |
int ma = -1, md = -1; | |
for (int d: g[p]) { | |
if (d == b) continue; | |
if (ma < sz[d]) { | |
ma = sz[d]; | |
md = d; | |
} | |
} | |
n2l[md] = P(n2l[p].first, n2l[p].second+1); | |
buf[n2l[p].second] = sz[p]-sz[md]; | |
bufsm[n2l[p].second+1] = bufsm[n2l[p].second] + buf[n2l[p].second]; | |
dfs(md, p); | |
for (int d: g[p]) { | |
if (d == b) continue; | |
if (d == md) continue; | |
n2l[d] = P(lc, 0); | |
l2p[lc] = n2l[p]; | |
ldps[lc] = ldps[n2l[p].first]+1; | |
lc++; | |
dfs(d, p); // light | |
} | |
} | |
void init() { | |
n2l[0] = P(0, 0); | |
l2p[0] = P(-1, 0); | |
ldps[0] = 0; | |
bufsm[0] = 0; | |
lc = 1; | |
dfs_sz(0, -1); | |
dfs(0, -1); | |
} | |
void data_set(int k, int x) { | |
li[n2l[k].first]->set(n2l[k].second, x); | |
} | |
void path_set(int u, int v, int d) { | |
int xl, xp; tie(xl, xp) = n2l[u]; | |
int yl, yp; tie(yl, yp) = n2l[v]; | |
if (ldps[xl] > ldps[yl]) { | |
while (ldps[xl] > ldps[yl]) { | |
li[xl]->set(0, xp+1, d); | |
tie(xl, xp) = l2p[xl]; | |
} | |
} else if (ldps[xl] < ldps[yl]) { | |
while (ldps[xl] < ldps[yl]) { | |
li[yl]->set(0, yp+1, d); | |
tie(yl, yp) = l2p[yl]; | |
} | |
} | |
while (xl != yl) { | |
assert(ldps[xl] == ldps[yl]); | |
li[xl]->set(0, xp+1, d); | |
tie(xl, xp) = l2p[xl]; | |
li[yl]->set(0, yp+1, d); | |
tie(yl, yp) = l2p[yl]; | |
} | |
if (xp > yp) { | |
li[xl]->set(yp, xp+1, d); | |
} else { | |
li[yl]->set(xp, yp+1, d); | |
} | |
} | |
Tree::Node path_get(int u, int v) { | |
int xl, xp; tie(xl, xp) = n2l[u]; | |
int yl, yp; tie(yl, yp) = n2l[v]; | |
Tree::Node nl, nr; | |
if (ldps[xl] > ldps[yl]) { | |
while (ldps[xl] > ldps[yl]) { | |
nl = Tree::merge(li[xl]->get(0, xp+1), nl); | |
tie(xl, xp) = l2p[xl]; | |
} | |
} else if (ldps[xl] < ldps[yl]) { | |
while (ldps[xl] < ldps[yl]) { | |
nr = Tree::merge(li[yl]->get(0, yp+1), nr); | |
tie(yl, yp) = l2p[yl]; | |
} | |
} | |
while (xl != yl) { | |
assert(ldps[xl] == ldps[yl]); | |
nl = Tree::merge(li[xl]->get(0, xp+1), nl); | |
tie(xl, xp) = l2p[xl]; | |
nr = Tree::merge(li[yl]->get(0, yp+1), nr); | |
tie(yl, yp) = l2p[yl]; | |
} | |
if (xp > yp) { | |
nl = Tree::merge(li[xl]->get(yp, xp+1), nl); | |
} else { | |
nr = Tree::merge(li[yl]->get(xp, yp+1), nr); | |
} | |
nl = Tree::rev(nl); | |
return Tree::merge(nl, nr); | |
} | |
}; | |
const int MN = 200100; | |
HLComp_Y<MN> hl; | |
//時間計測は闇が多いことに注意 | |
//codeforcesで動作確認 | |
namespace StopWatch { | |
clock_t st; | |
bool f = false; | |
void start() { | |
f = true; | |
st = clock(); | |
} | |
int msecs() { | |
assert(f); | |
return (clock()-st)*1000 / CLOCKS_PER_SEC; | |
} | |
} | |
int w[MN]; | |
int main2() { | |
StopWatch::start(); | |
int n, q; | |
bool debf = false; | |
scanf("%d %d", &n, &q); //# of node | |
for (int i = 0; i < n; i++) { | |
scanf("%d", w+i); | |
} | |
if (n >= 2 && w[0] == 1569 && w[1] == 5389) { | |
debf = true; | |
} | |
for (int i = 0; i < n-1; i++) { | |
int s, e; | |
scanf("%d %d", &s, &e); s--; e--; | |
hl.add(s, e); | |
} | |
hl.init(); | |
if (debf && StopWatch::msecs() >= 100) { | |
// return 0; | |
} | |
cerr << StopWatch::msecs() << endl; | |
for (int i = 0; i < n; i++) { | |
hl.data_set(i, w[i]); | |
} | |
for (int i = 0; i < q; i++) { | |
int t, a, b, c; | |
scanf("%d %d %d %d", &t, &a, &b, &c); a--; b--; | |
if (t == 1) { | |
hl.path_set(a, b, c); | |
} else { | |
auto n = hl.path_get(a, b); | |
printf("%d\n", (n.mv < 0) ? n.mv : n.ma); | |
} | |
} | |
// cerr << dc << endl; | |
return 0; | |
} | |
/*AOJ用 stack sizeを拡張する*/ | |
signed main() { | |
#ifndef __APPLE__ | |
static ll eord, enew; | |
const int sz = 32*1024*1024; | |
static void *p = malloc(sz); | |
enew = (long long)p + sz - 1; | |
__asm__ volatile("mov %%rsp, %0" : "=r"(eord)); | |
__asm__ volatile("mov %0, %%rsp" : : "r"(enew)); | |
#endif | |
main2(); | |
#ifndef __APPLE__ | |
__asm__ volatile("mov %0, %%rsp" : : "r"(eord)); | |
#endif | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment