Skip to content

Instantly share code, notes, and snippets.

@yosupo06
Created October 2, 2015 13:57
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save yosupo06/cc541057225e647bd36c to your computer and use it in GitHub Desktop.
#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