题意：三种操作 ①修改第i条边的权值为val，②把u到v路径上的所有边的权值 去相反数③求u 到v路径上最大的边权
线段树的区间更新还是不熟练，，一直搞不对调试了好久还是没对，最后还是看的kuangbin的代码。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5+;
struct
{
int to,next;
}e[maxn<<];
int head[maxn],edge;
void add(int x,int y)
{
e[edge].to = y;
e[edge].next = head[x];
head[x] = edge++;
}
int son[maxn],fa[maxn],siz[maxn],dep[maxn];
void dfs(int root)
{
siz[root] = ;
son[root] = ;
for (int i = head[root]; i > ; i = e[i].next)
{
if (fa[root] != e[i].to)
{
dep[e[i].to] = dep[root] + ;
fa[e[i].to] = root;
dfs(e[i].to);
if (siz[e[i].to] > siz[son[root]])
son[root] = e[i].to;
siz[root] += siz[e[i].to];
}
}
}
int tot,top[maxn],li[maxn<<],pos[maxn];
void build(int root,int father)
{
top[root] = father;
pos[root] = tot;
li[tot++] = root;
if (son[root] > )
build(son[root],top[root]);
for (int i = head[root]; i > ; i = e[i].next)
if (fa[root] != e[i].to && son[root] != e[i].to)
build(e[i].to,e[i].to);
} int minv[maxn<<],maxv[maxn<<], tt[maxn],lazy[maxn<<];
void build_Segtree(int l,int r,int o)
{
lazy[o] = ;
if (l == r)
{
minv[o] = tt[li[l]];
maxv[o] =tt[li[l]];
return;
}
int mid = (l + r) >> ;
build_Segtree(l,mid,o<<);
build_Segtree(mid+,r,o<<|);
minv[o] = min(minv[o<<],minv[o<<|]);
maxv[o] = max(maxv[o<<],maxv[o<<|]);
}
char op[];
int val;
inline void push_down(int l,int r,int o)
{
if (lazy[o]&&l!=r)
{
maxv[o<<] = -maxv[o<<];
minv[o<<] = -minv[o<<];
maxv[o<<|] = -maxv[o<<|];
minv[o<<|] = -minv[o<<|];
swap(maxv[o<<],minv[o<<]);
swap(maxv[o<<|],minv[o<<|]);
lazy[o<<] ^= ;
lazy[o<<|] ^= ;
lazy[o] = ;
}
}
void update(int l,int r,int o,int ua,int ub)
{
if (ua <= l && ub >= r)
{
if (op[] == 'N')
{
maxv[o] = -maxv[o];
minv[o] = -minv[o];
swap(maxv[o],minv[o]);
lazy[o] ^= ;
}
if (op[] == 'C')
minv[o] = maxv[o] = val,lazy[o] = ;
return;
}
//if (op[0] == 'N')
push_down(l,r,o);
int mid = (l + r) >> ;
if (ua <= mid)
update(l,mid,o<<,ua,ub);
if (ub > mid)
update(mid+,r,o<<|,ua,ub);
minv[o] = min(minv[o<<],minv[o<<|]);
maxv[o] = max(maxv[o<<],maxv[o<<|]);
} int query(int l,int r,int o,int ua,int ub)
{
if (ua <= l && ub >= r)
return maxv[o];
int mid = (l + r) >> ;
push_down(l,r,o);
int t1 = -inf,t2 = -inf;
if (ua <= mid)
t1 = query(l,mid,o<<,ua,ub);
if (ub > mid)
t2 = query(mid+,r,o<<|,ua,ub);
minv[o] = min(minv[o<<],minv[o<<|]);
maxv[o] = max(maxv[o<<],maxv[o<<|]);
return max(t1,t2);
} int get_max(int ua,int ub)
{
int f1 = top[ua];
int f2 = top[ub];
int tmp = -inf;
while (f1 != f2)
{
if (dep[f1] < dep[f2])
swap(ua,ub),swap(f1,f2);
tmp = max(tmp,query(,tot,,pos[f1],pos[ua]));
ua = fa[f1];
f1 = top[ua];
}
if (ua == ub)
return tmp;
if (dep[ua] > dep[ub])
swap(ua,ub);
return tmp = max(tmp,query(,tot,,pos[son[ua]],pos[ub]));
}
void get_negate(int ua,int ub)
{
int f1 = top[ua];
int f2 = top[ub];
while (f1 != f2)
{
if (dep[f1] < dep[f2])
swap(ua,ub),swap(f1,f2);
update(,tot,,pos[f1],pos[ua]);
ua = fa[f1];
f1 = top[ua];
}
if (dep[ua] > dep[ub])
swap(ua,ub);
if (ua == ub)
return;
update(,tot,,pos[son[ua]],pos[ub]);
} int d[maxn][];
void init()
{
int root,n;
scanf ("%d",&n);
root = (n + ) >> ;
edge = tot = ;
memset(siz,,sizeof(siz));
memset(head,,sizeof(head));
fa[root] = dep[root] = ;
for (int i = ; i < n; i++)
{
scanf ("%d%d%d",&d[i][],&d[i][],&d[i][]);
add(d[i][],d[i][]);
add(d[i][],d[i][]);
}
dfs(root);
build(root,root);
build_Segtree(,tot,);
op[] = 'C';
for (int i = ; i < n; i++)
{
if (dep[d[i][]] < dep[d[i][]])
swap(d[i][],d[i][]);
tt[d[i][]] = val = d[i][];
update(,tot,,pos[d[i][]],pos[d[i][]]);
}
}
int main(void)
{
freopen("in.txt","r",stdin);
int t;
scanf ("%d",&t);
while (t--)
{
init();
while (scanf ("%s",op),op[] != 'D')
{
int x,y;
scanf ("%d%d",&x,&y);
if (op[] == 'Q'&&x!=y)
printf("%d\n",get_max(x,y));
if (op[] == 'Q' && x == y)
printf("0\n");
if (op[] == 'C')
{
val = y;
update(,tot,,pos[d[x][]],pos[d[x][]]);
}
if (op[] == 'N'&&x!=y)
get_negate(x,y);
}
}
return ;
} /*
1
11
2 1 1
2 4 2
2 3 3
1 5 4
3 6 5
3 7 6
7 8 7
4 9 8
9 10 9
10 11 10
N 2 10
Query 4 10
DONE */