萌田薰子 @ 2018-10-24 21:31:09
查询思路是树剖lca 然后lca那个点丢掉
修改思路是邻接表找边 因为是双向就乘上2 找边连着的两点就×2和×2-1 更新值到dep更深的那个点上 然后就是寻常更新最大值= =
真改不出求dalao帮帮忙......
```
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 100005;
struct edge{int next,to,v;}e[MAXN << 1];
int siz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN],id[MAXN],oid[MAXN];
int first[MAXN],tr[MAXN << 3],v[MAXN],tot = 1;
inline int max(int x,int y) {return x > y ? x : y;}
inline int r()
{
char q = getchar(); int x = 0,y = 0;
while (q < '0' && q != '-' || q > '9') q = getchar();
if (q == '-') ++ y,q = getchar();
while ('0' <= q && q <= '9')
x = (x << 3) + (x << 1) + q - (3 << 4),q = getchar();
return y ? -x : x;
}
inline void add(int x,int y,int z)
{
e[++tot].next = first[x];
e[tot].to = y;
e[tot].v = z;
first[x] = tot;
}
inline void dfs1(int p)
{
++siz[p];
dep[p] = dep[fa[p]] + 1;
for (int a = first[p],b = e[a].to ; a ; a = e[a].next,b = e[a].to)
if (b != fa[p])
{
v[b] = e[a].v;
fa[b] = p;
dfs1(b);
siz[p] += siz[b];
if (siz[son[p]] < siz[b]) son[p] = b;
}
}
inline void dfs2(int p,int f)
{
id[p] = ++tot;
oid[p] = tot;
top[p] = f;
if (!son[p]) return;
dfs2(son[p],f);
for (int a = first[p],b = e[a].to ; a ; a = e[a].next,b = e[a].to)
if (b != son[p] && b != fa[p]) dfs2(b,b);
}
inline void build(int l,int r,int len)
{
if (l == r) {tr[len] = v[oid[l]]; return;}
int mid = (l + r) >> 1;
build(l,mid,len << 1);
build(++mid,r,len << 1 | 1);
tr[len] = max(tr[len << 1],tr[len << 1 | 1]);
}
inline int get(int l,int r,int len,int i,int j)
{
if (i <= l && r <= j) return tr[len];
int mid = (l + r) >> 1,ans = -0x7fffffff;
if (i <= mid) ans = max(ans,get(l,mid,len << 1,i,j));
if (mid < j) ans = max(ans,get(++mid,r,len << 1 | 1,i,j));
return ans;
}
inline int out(int x,int y)
{
int ans = -0x7fffffff;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x,y);
ans = max(ans,get(1,siz[1],1,id[top[x]],id[x]));
x = fa[top[x]];
}
if (x == y) return ans;
if (dep[x] > dep[y]) swap(x,y);
for (int a = first[x],b = e[a].to ; a ; a = e[a].next,b = e[a].to)
if (top[b] == top[y]) {x = b; break;}
return max(ans,get(1,siz[1],1,id[x],id[y]));
}
inline void update(int l,int r,int len,int i)
{
if (l == r && l == i) {tr[len] = v[oid[i]]; return;}
int mid = (l + r) >> 1;
if (i <= mid) update(l,mid,len << 1,i);
else update(++mid,r,len << 1 | 1,i);
tr[len] = max(tr[len << 1],tr[len << 1 | 1]);
}
inline void getedge()
{
int x = r();
x = dep[e[x << 1].to] > dep[e[(x << 1) - 1].to] ? e[x << 1].to : e[(x << 1) - 1].to;
v[x] = r();
update(1,siz[1],1,id[x]);
}
int main()
{
int n = r();
for (int a = 1 ; a < n ; ++ a)
{
int x = r(),y = r(),z = r();
add(x,y,z),add(y,x,z);
}
tot = 0;
dfs1(1);
dfs2(1,1);
build(1,n,1);
char q[1 << 3];
while (~scanf("%s",q))
if (q[0] == 'Q') printf("%d\n",out(r(),r())); else
if (q[0] == 'C') getedge(); else break;
return 0;
}
```