题目大意：
一棵树，有边权，有两个操作：1.修改一条边的权值；2.询问两点间路径上的边的权值的最大值。
思路：
十分裸的树链剖分+线段树，无非是边权要放到深度大的一端的点上，但是有两个坑爹的地方，改了好久：
1.数组定义10000和40000会TLE，要乘10；
2.以前的树剖求解的最后是这样的：
if (deep[x]>deep[y]) swap(x,y); return max(ans,MAX(1,n,id[x],id[y],1));但是WA了，膜拜大神后发现这样就AC了：
if (x==y) return ans; if (dep[x]>dep[y]) swap(x,y); return max(ans,ask(1,n,id[x]+1,id[y],1));以前应该是错了。
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int M=100009; 5 int n,cnt,t,p[M],hea[M],size[M],v[M],a[M],b[M],c[M],nex[M],dep[M],top[M],id[M],tree[M<<2]; 6 char s[M]; bool vis[M]; 7 8 int read() 9 { 10 int x=0; bool f=0; char ch=getchar(); 11 while (ch<'0' || ch>'9') { if (ch=='-') f=1; ch=getchar(); } 12 while (ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 13 return f?-x:x; 14 } 15 16 void add(int x,int y) { v[++cnt]=y,nex[cnt]=hea[x],hea[x]=cnt; } 17 18 void dfs1(int x,int fa,int h) 19 { 20 size[x]=1,dep[x]=h,p[x]=fa; 21 for (int i=hea[x],y;i;i=nex[i]) 22 if ((y=v[i])^fa) dfs1(y,x,h+1),size[x]+=size[y]; 23 } 24 25 void dfs2(int x,int chain) 26 { 27 int i,k=0,y; 28 id[x]=++t,top[x]=chain; 29 for (i=hea[x];i;i=nex[i]) 30 if (size[y=v[i]]>size[k] && y^p[x]) k=y; 31 if (!k) return; dfs2(k,chain); 32 for (i=hea[x];i;i=nex[i]) 33 if ((y=v[i])^p[x] && k^y) dfs2(y,y); 34 } 35 36 void push_up(int k) { tree[k]=max(tree[k<<1],tree[k<<1|1]); } 37 38 void change(int L,int R,int x,int val,int cur) 39 { 40 if (L==R) { tree[cur]=val; return; } 41 int mid=L+R>>1; 42 if (x>mid) change(mid+1,R,x,val,cur<<1|1); 43 else change(L,mid,x,val,cur<<1); 44 push_up(cur); 45 } 46 47 int ask(int L,int R,int l,int r,int cur) 48 { 49 if (l<=L && R<=r) return tree[cur]; 50 int mid=L+R>>1; 51 if (r<=mid) return ask(L,mid,l,r,cur<<1); 52 else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1); 53 else return max(ask(L,mid,l,mid,cur<<1),ask(mid+1,R,mid+1,r,cur<<1|1)); 54 } 55 56 int qry(int x,int y) 57 { 58 int ans=-10000000; 59 for (;top[x]^top[y];x=p[top[x]]) 60 { 61 if (dep[top[x]]<dep[top[y]]) swap(x,y); 62 ans=max(ans,ask(1,n,id[top[x]],id[x],1)); 63 } 64 if (x==y) return ans; 65 if (dep[x]>dep[y]) swap(x,y); 66 return max(ans,ask(1,n,id[x]+1,id[y],1)); 67 } 68 69 int main() 70 { 71 for (int T=read(),i;T;--T) 72 { 73 n=read(),cnt=t=0; 74 for (i=0;i<=n;++i) hea[i]=0; 75 for (i=1;i<n;++i) 76 { 77 a[i]=read(),b[i]=read(),c[i]=read(); 78 add(a[i],b[i]),add(b[i],a[i]); 79 } 80 dfs1(1,1,1),dfs2(1,1); 81 for (i=1;i<n;++i) 82 { 83 if (dep[a[i]]<dep[b[i]]) swap(a[i],b[i]); 84 change(1,n,id[a[i]],c[i],1); 85 } 86 for (;;) 87 { 88 scanf("%s",s); 89 if (s[0]=='D') break; 90 int x=read(),y=read(); 91 if (s[0]=='C') change(1,n,id[a[x]],y,1); 92 if (s[0]=='Q') printf("%d\n",qry(x,y)); 93 } 94 } 95 return 0; 96 }转载于:https://www.cnblogs.com/HHshy/p/6368228.html
相关资源：JAVA上百实例源码以及开源项目