新模板，配合新线段树版本了：
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <tr1/unordered_map>
using std::tr1::unordered_map;
//using std::setiosflags;
//using std::setprecision;
using std::sort;
using std::max;
using std::min;
using std::cout;
using std::stack;
using std::cin;
using std::endl;
using std::swap;
using std::pair;
using std::vector;
using std::set;
using std::map;
using std::make_pair;
using std::multiset;
using std::unique;
using std::queue;
using std::greater;
using std::string;
using std::priority_queue;
using std::lower_bound;//返回第一个不小于
using std::upper_bound;//返回第一个大于
using std::max_element;
using std::min_element;
using __gnu_pbds::pairing_heap_tag;
#define Hash unordered_map
#define clr(x) memset(x,0,sizeof(x))
#define logz(x) (31-__builtin_clz((int)x))
#define logzl(x) (63-__builtin_clzll((LL)x))
#define cf std::ios::sync_with_stdio(0);std::cin.tie(0)
typedef unsigned long long uLL;
typedef long long LL;
const double PI = acos(-1);
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100100;
const int inf = 0x7fffffff;
//----建边部分
struct Vector_edge//存vector用的东西
{
int will, w;//v为连接的点， w为边权
Vector_edge():will(0),w(0){}
Vector_edge(int a, int b):will(a),w(b){}
};
vector<Vector_edge>g[maxn];
struct edge
{
int to, next;
}e[maxn];
inline void add_edge(int a, int b, int c)
{
g[a].push_back(Vector_edge(b,c));
}
//----树链部分=====
int dfs_clock;//DFS时间序列
struct node
{
int size, dep, son, top, fa, ti;
node():size(0),dep(0),son(0),top(0),fa(0),ti(0){};
//size:v为跟节点数量
//dep:v的深度 根为1
//top:v所在链的顶端
//son:vv在同一重链的儿子节点，重儿子
//ti:v与父亲的连边，在线段树中的位置
}t[maxn];
void dfs_find(int u, int pa, int depth)//第一次DFS，得到size,dep,fa以及son的数据
{
t[u].son = 0; //重儿子，为0表示没有重儿子
t[u].size = 1; //节点数量
t[u].dep = depth;
t[u].fa = pa;
for (int i = 0; i != g[u].size(); ++ i)
{
int will = g[u][i].will;
if (will == pa) continue;
dfs_find(will, u, depth + 1);
t[u].size += t[will].size;
if (t[will].size > t[t[u].son].size) t[u].son = will;
}
}
void dfs_time(int u, int pa) // 得到时间戳等数据,u为当前节点，pa为父链顶端节点
{
t[u].ti = ++ dfs_clock; //u这个节点的时间戳是dfs_clock,dfs_clock下标是从1开始的，没有0！
t[u].top = pa; //top是u所在链的顶端
if (t[u].son != 0) dfs_time(t[u].son, t[u].top); //如果节点有重儿子，那么依旧是以pa为链顶端的一条链
for (int i = 0; i != g[u].size(); ++ i)
{
int will = g[u][i].will;
if (will == t[u].son || will == t[u].fa) continue;//重儿子或者父节点，则跳过
dfs_time(will, will);//新的一条链
}
}
//----线段树部分--
int val[maxn<<2], mx[maxn<<2];
#define lson o*2, L, M
#define rson o*2+1, M + 1,R
int segment_tree_query_l, segment_tree_query_r, segment_tree_query_ans;
//int segment_tree_update_l, segment_tree_update_r, segment_tree_update_val;
//这种线段树写法，需要把询问的东西，放在全局变量
//qans就是query询问的结果，ql,qr是询问[L,R]区间的答案
//ql,qr,qans对于update的时候，本着不浪费的原则，复用一下，就不用upl,upr,和upval了
#define qans segment_tree_query_ans
#define ql segment_tree_query_l
#define qr segment_tree_query_r
//upl ,upr是update的[L,R]区间，改为upval
#define upl segment_tree_update_l
#define upr segment_tree_update_r
#define upval segment_tree_update_val
int n;
void update(int o, int L, int R)// L,R区间统一改为qans
{
if (ql <= L && R <= qr)
{
val[o] = mx[o] = qans;
return ;
}
int M = L + (R - L) / 2;
if (ql <= M) update(lson);
if (qr > M) update(rson);
mx[o] = max(mx[o*2], mx[o*2+1]);
}
void query(int o, int L, int R)
{
if (ql <= L && R <= qr)
{
qans= max(qans, mx[o]);
return ;
}
int M = L + (R- L)/2;
if (ql <= M) query(lson);
if (qr > M) query(rson);
}
int lca(int x, int y)//找出x到y的之间所有的区间
{
int ans = -inf;
//cout<<t[x].top <<" " << t[y].top<<endl;
while (t[x].top != t[y].top)
{
if (t[t[x].top].dep < t[t[y].top].dep) swap(x,y); //x深，y浅
//线段树查询begin
qans= -inf;//切记要初始化qans
ql=t[t[x].top].ti;
qr=t[x].ti;
query(1,1,n);
ans = max(ans, qans);
//线段树查询end
x = t[t[x].top].fa;
}
if (t[x].dep > t[y].dep) swap(x, y);//x是上面一些的节点
if (x != y)
{
//线段树查询begin
qans= -inf;
ql=t[x].ti + 1;//一定要+1，因为x,y在一条链上，所以标号连续。
qr=t[y].ti;
query(1,1,n);
ans = max(ans, qans);
//线段树查询end
}
return ans;
}
int da[maxn][3];//起点, 终点, 权重
void clear()
{
dfs_clock = 0;
for (int i = 0; i != maxn; ++ i) g[i].clear();
memset(mx, 0, sizeof(mx));
memset(val, 0, sizeof(val));
}
int main()
{
int T; scanf("%d", &T);
while (T--)
{
clear();
scanf("%d", &n);
for (int i = 1; i < n; ++ i)
{
scanf("%d%d%d", &da[i][0], &da[i][1], &da[i][2]);
add_edge(da[i][0], da[i][1], da[i][2]);
add_edge(da[i][1], da[i][0], da[i][2]);
}
dfs_find(1, 1, 1);
dfs_time(1, 1);
for (int i = 1; i < n; i ++ )//人工更新所有的边
{
if (t[da[i][0]].dep > t[da[i][1]].dep)//相邻的边，一定是父子关系
swap(da[i][0] , da[i][1]);//da[i][1]是深度深的点, 然后da[i][1]这个点的DFS序号，就是他的前驱边的序号
//线段树update begin
ql = t[da[i][1]].ti;
qr = t[da[i][1]].ti;
qans = da[i][2];
update(1,1,n);
//线段树update end
}
char he[100];
while(1)
{
scanf("%s",he);
if(he[0]=='D')break;
if(he[0]=='Q')
{
int a,b;scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
else
{
int a,b;scanf("%d%d",&a,&b);
//线段树update begin
ql = t[da[a][1]].ti;
qr = t[da[a][1]].ti;
qans = b;
update(1,1,n);
//线段树update end
}
}
printf("\n");
}
return 0;
}
/*
1
5
1 2 3
1 3 1
3 4 3
1 5 3
QUERY 1 4
DONE
*/
模板
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 100100;
const int inf = 0x7fffffff;
//----建边部分
struct Vector_edge//存vector用的东西
{
int v, w;
Vector_edge():v(0),w(0){}
Vector_edge(int a, int b):v(a),w(b){}
};
vector<Vector_edge>g[maxn];
struct edge
{
int to, next;
}e[maxn];
inline void add_edge(int a, int b, int c)
{
g[a].push_back(Vector_edge(b,c));
}
//----树链部分=====
int dfs_clock, cnt;
struct node
{
int size, dep, son, top, fa, ti;
node():size(0),dep(0),son(0),top(0),fa(0),ti(0){};
//size:v为跟节点数量
//dep:v的深度 根为1
//top:v所在链的顶端
//son:vv在同一重链的儿子节点，重儿子
//ti:v与父亲的连边，在线段树中的位置
}t[maxn];
void dfs_find(int u, int pa, int depth)
{
//cout<<u<<" "<<pa<<" "<<depth<<endl;
t[u].son = 0;
t[u].size = 1;
t[u].dep = depth;
t[u].fa = pa;
for (int i = 0; i != g[u].size(); ++ i)
{
int v = g[u][i].v;
if (v == pa) continue;
dfs_find(v, u, depth + 1);
t[u].size += t[v].size;
//if (t[u].son == -1) t[u].son = v;
if (t[v].size > t[t[u].son].size) t[u].son = v;
}
}
void dfs_time(int u, int pa)
{
t[u].ti = ++ dfs_clock; t[u].top = pa;
if (t[u].son != 0) dfs_time(t[u].son, t[u].top);
for (int i = 0; i != g[u].size(); ++ i)
{
int v = g[u][i].v;
if (v == t[u].son || v == t[u].fa) continue;
dfs_time(v, v);
}
}
//----线段树部分--
struct xianduan_node
{
int l,r,val,mx;
int mid(){return (l+r)>>1;}
}tree[maxn<<2];
void build(int pos, int l, int r)
{
tree[pos].l = l;
tree[pos].r = r;
tree[pos].mx = tree[pos].val = - inf;
if (l == r) return;
int mid = tree[pos].mid();
build(lson,l,mid);
build(rson, mid + 1, r);
}
void update(int pos, int id, int w)// id改为w
{
if (tree[pos].l == tree[pos].r)
{
tree[pos].mx = tree[pos].val = w;
return ;
}
int mid = tree[pos].mid();
if (mid >= id) update(lson, id, w);
else update(rson, id, w);
tree[pos].mx = max(tree[lson].mx, tree[rson].mx);
}
int query(int pos, int L, int R)
{
//cout<<L<<" "<<R<<" "<<pos<<" "<<tree[pos].l<<" "<<tree[pos].r<<" "<<tree[pos].mx<<endl;
if (L <= tree[pos].l && tree[pos].r <= R)
return tree[pos].mx;
int mid = tree[pos].mid();
int ans = - inf;
if (mid >= L) ans = max(ans, query(lson, L, R));
if (mid < R) ans = max(ans, query(rson, L, R));
return ans;
}
int lca(int x, int y)
{
int ans = -inf;
while (t[x].top != t[y].top)
{
if (t[t[x].top].dep < t[t[y].top].dep) swap(x,y);
ans = max(ans, query(1, t[t[x].top].ti, t[x].ti));
x = t[t[x].top].fa;
}
if (t[x].dep > t[y].dep) swap(x, y);
//cout<<x<<" "<<y<<endl;
//cout<<ans<<endl;
//cout<<t[x].ti<<" "<<t[y].ti<<endl;
//cout<<endl<<endl;
if (x != y) ans = max(ans , query(1, t[x].ti + 1, t[y].ti));
这里的t[x].ti指的是x与其父亲的边，所以一定注意+1
return ans;
}
int n;
int da[maxn][3];
void clear()
{
cnt = dfs_clock = 0;
for (int i = 0; i != maxn; ++ i) g[i].clear();
}
int main()
{
int T; scanf("%d", &T);
while (T--)
{
clear();
scanf("%d", &n);
for (int i = 1; i < n; ++ i)
{
scanf("%d%d%d", &da[i][0], &da[i][1], &da[i][2]);
add_edge(da[i][0], da[i][1], da[i][2]);
add_edge(da[i][1], da[i][0], da[i][2]);
}
dfs_find(1, 1, 1);
dfs_time(1, 1);
build(1, 2, n);//因为1没有前驱边，1是树根
for (int i = 1; i < n; i ++ )
{
if (t[da[i][0]].dep > t[da[i][1]].dep)
swap(da[i][0] , da[i][1]);
update(1, t[da[i][1]].ti, da[i][2]);
}
char he[100];
while(1)
{
scanf("%s",he);
if(he[0]=='D')break;
if(he[0]=='Q')
{
int a,b;scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
else
{
int a,b;scanf("%d%d",&a,&b);
update(1,t[da[a][1]].ti,b);
}
}
printf("\n");
}
return 0;
}
/*
1
5
1 2 3
1 3 1
3 4 3
1 5 3
QUERY 1 4
DONE
*/