记录一个菜逼的成长。。
题目链接 题目大意： 给你n个点树，有两种操作 1.CHANGE i ti :将第i条边的值改为ti 2.QUERY a b :查询a点到b点的路径上的最大值
跟上题类似，不过这题还简单点，没有取反操作。 直接套就行了。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define fin freopen("D://in.txt","r",stdin) #define fout freopen("D://out.txt","w",stdout) #define cl(a,b) memset(a,b,sizeof(a)) #define lson t<<1,l,mid #define rson t<<1|1,mid+1,r const int maxn = 200000 + 10; const int INF = 0x3f3f3f3f; int eg[maxn][3]; int head[maxn],cnt; struct Edge{ int to,next; }edge[maxn<<1]; void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } int num; int val[maxn],siz[maxn],dep[maxn],son[maxn]; int top[maxn],tid[maxn],pos[maxn],fa[maxn]; void init() { cl(head,-1);cl(son,-1); cnt = num = 0; } ///树链剖分部分 void dfs1(int u,int father,int d) { dep[u] = d; fa[u] = father; siz[u] = 1; for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if(v != father) { dfs1(v,u,d+1); siz[u] += siz[v]; if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v; } } } void dfs2(int u,int tp) { top[u] = tp; tid[u] = ++num; pos[tid[u]] = u; if(son[u] == -1) return; dfs2(son[u],tp); for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if(v != son[u] && v != fa[u]) dfs2(v,v); } } ///线段树部分 struct Node{ int l,r,mx; }node[maxn<<2]; void pushup(int t) { node[t].mx = max(node[t<<1].mx, node[t<<1|1].mx); } void build(int t,int l,int r) { node[t].l = l; node[t].r = r; if(l == r){ node[t].mx = 0; return ; } int mid = (l + r) >> 1; build(lson); build(rson); pushup(t); } void update(int t,int ind,int v) { if(node[t].l == node[t].r && node[t].l == ind){ node[t].mx = v; return ; } int mid = (node[t].l + node[t].r) >> 1; if(ind <= mid)update(t<<1,ind,v); else update(t<<1|1,ind,v); pushup(t); } int query(int t,int l,int r) { if(node[t].l >= l && node[t].r <= r){ return node[t].mx; } int ret = -INF; int mid = (node[t].l + node[t].r) >> 1; if(l <= mid)ret = max(ret,query(t<<1,l,r)); if(r > mid)ret = max(ret,query(t<<1|1,l,r)); pushup(t); return ret; } int solveMax(int x,int y) { int ret = -INF; while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]])swap(x,y); ret = max(ret,query(1,tid[top[x]],tid[x])); x = fa[top[x]]; } if(x == y)return ret; if(dep[x] > dep[y])swap(x,y); return max(ret,query(1,tid[son[x]],tid[y])); } int main() { //fin,fout; char ope[10]; int T,n;scanf("%d",&T); while(T--){ scanf("%d",&n); init(); for( int i = 1; i < n; i++ ){ scanf("%d%d%d",&eg[i][0],&eg[i][1],&eg[i][2]); add(eg[i][0],eg[i][1]); add(eg[i][1],eg[i][0]); } dfs1(1,0,0); dfs2(1,1); build(1,1,n); for( int i = 1; i < n; i++ ){ if(dep[eg[i][0]] < dep[eg[i][1]])swap(eg[i][0],eg[i][1]); update(1,tid[eg[i][0]],eg[i][2]); } int a,b; while(scanf("%s",ope) && ope[0] != 'D'){ scanf("%d%d",&a,&b); if(ope[0] == 'Q'){ printf("%d\n",solveMax(a,b)); } if(ope[0] == 'C'){ update(1,tid[eg[a][0]],b); } } } return 0; }