Skip to content

Instantly share code, notes, and snippets.

@lazycal
Created April 18, 2014 07:26
  • 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 lazycal/11029304 to your computer and use it in GitHub Desktop.
QTREE1
#include <cstdio>
#include <algorithm>
const int N = 100000 + 9;
int lc[N * 2],rc[N * 2],Max[N * 2],n,ec,son[N],fa[N],tp[N],rt[N],d[N],nxt[N * 2],head[N * 2],lnk[N * 2],cost[N * 2],tot[N],maxch[N],sz[N],c[N];
int L,R,cnt,t[N];
char s[100];
int build(const int l,const int r)
{
int idx = ++cnt;
if (l == r) {Max[idx] = c[t[l]];return idx;}
const int mid = (l + r) / 2;
lc[idx] = build(l,mid);
rc[idx] = build(mid + 1,r);
Max[idx] = std::max(Max[lc[idx]],Max[rc[idx]]);
return idx;
}
void build(int x)
{
int top = x;
for (t[0] = 0; x; x = maxch[x]) tp[x] = top,t[++t[0]] = x;
tot[top] = t[0];
rt[top] = build(1,tot[top]);
}
void modify(const int idx,const int l,const int r,const int v)
{
if (l == r) return (void)(Max[idx] = v);
const int mid = (l + r) / 2;
if (L <= mid) modify(lc[idx],l,mid,v);
else modify(rc[idx],mid + 1,r,v);
Max[idx] = std::max(Max[lc[idx]],Max[rc[idx]]);
}
void modify(const int x,const int v)
{
L = d[x] - d[tp[x]] + 1;
modify(rt[tp[x]],1,tot[tp[x]],v);
}
int query(const int idx,const int l,const int r)
{
if (L <= l && r <= R) return Max[idx];
int res = -0x3f3f3f3f,mid = (l + r) / 2;
if (L <= mid) res = std::max(res,query(lc[idx],l,mid));
if (mid < R) res = std::max(res,query(rc[idx],mid + 1,r));
return res;
}
int Q(const int u,const int l,const int r)
{
L = l - d[u] + 1; R = r - d[u] + 1;
return query(rt[u],1,tot[u]);
}
int query(int u,int v)
{
int res = -0x3f3f3f3f;
while (tp[u] != tp[v]) {
if (d[tp[u]] < d[tp[v]]) std::swap(u,v);
res = std::max(res,Q(tp[u],d[tp[u]],d[u]));
u = fa[tp[u]];
}
if (d[u] < d[v]) std::swap(u,v);
res = std::max(res,Q(tp[u],d[v] + 1,d[u]));
return res;
}
void dfs(const int u)
{
for (int v,i = son[u]; i; i = nxt[i]) {
if (lnk[i] == fa[u]) continue;
fa[v = lnk[i]] = u;
d[v] = d[u] + 1;
c[v] = cost[i];
dfs(v);
sz[u] += sz[v];
if (sz[maxch[u]] < sz[v]) {
if (maxch[u]) build(maxch[u]);
maxch[u] = v;
}else build(v);
}
++sz[u];
}
inline void addedge(const int x,const int y,const int z)
{
nxt[++ec] = son[x];
son[x] = ec;
lnk[ec] = y;
cost[ec] = z;
head[ec] = x;
}
int main()
{
int T;
scanf("%d",&T);
for (int x,y,z; T--; ) {
ec = 0;
scanf("%d",&n);
for (int i = 1; i <= n; ++i) maxch[i] = sz[i] = son[i] = 0;
for (int i = 1; i < n; ++i) {
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z); addedge(y,x,z);
}
d[1] = 1;
dfs(1);
build(1);
scanf("%s",s);
while (s[0] != 'D') {
scanf("%d%d",&x,&y);
if (s[0] == 'Q') printf("%d\n",query(x,y));
else if (fa[head[x * 2]] == lnk[x * 2]) modify(head[x * 2],y);
else modify(lnk[x * 2],y);
scanf("%s",s);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment