SPOJ太慢了，SPOJ太慢了，
题意：给定n(n<=10000)个节点的树，每条边有边权，有两种操作：1.修改某条变的边权；2.查询u，v之间路径上的最大边权。
分析：树链剖分入门题，看这里：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
轻重链剖分，线段树维护，复杂度 O(nlogn + q* logn * logn )
SPOJ太慢了，我知道我写的应该是没错了，
最后把自己宏定义的max和min去掉之后终于过了，傻逼笑呵呵了。。为啥宏定义max，min占用这么长时间，求指教。
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std; #define maxn 10010 int w[maxn],son[maxn],sz[maxn],top[maxn],fa[maxn],dep[maxn]; int d1[maxn][3]; int z; int n ; char str[15]; struct node { int v ,next; }; node e[maxn * 2 ]; int cnt ; int head[maxn]; int tt[maxn * 3 ]; inline void add(int u ,int v) { e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++ ; return ; } void push_up(int root ) { tt[root] = max(tt[root*2],tt[root*2+1]); } inline void dfs1(int u ) // 计算 sz[],son[],dep[],fa[]; { sz[u] = 1 ; son[u] = 0; for(int i = head[u] ; i != -1 ; i = e[i].next) if(e[i].v != fa[u]) { fa[e[i].v] = u; dep[e[i].v] = dep[u] + 1; dfs1(e[i].v); if(sz[e[i].v] > sz[son[u]] ) son[u] = e[i].v; sz[u] += sz[e[i].v]; } } void dfs2(int u,int tp) // 计算 w[],top[] { w[u] = ++ z ; top[u] = tp; if(son[u] != 0 ) dfs2(son[u] , top[u]); for(int i = head[u] ; i!= -1 ;i = e[i].next) if(e[i].v != fa[u] && e[i].v != son[u] ) dfs2(e[i].v,e[i].v); return ; } void update(int root,int l,int r,int pos,int val) { if(l == r ) { tt[root] = val; return ; } int mid = (l + r ) / 2; if(pos <= mid) update(root + root ,l,mid, pos , val); else update(root + root + 1 ,mid +1 , r , pos ,val); push_up(root); return ; } int query(int root,int l1,int r1,int l,int r) { if(l <= l1 && r1 <= r) return tt[root]; int mid = (l1 + r1 ) / 2 ; int res = 0 ; if(l <= mid ) res = max(res , query(root + root,l1 , mid , l , r )); if(r > mid ) res = max(res , query(root + root + 1 ,mid + 1 , r1 , l , r )); return res; } int find(int a,int b) { int f1 = top[a] , f2 = top[b] , tmp = 0 ; while( f1 != f2 ) { if(dep[f1] < dep[f2]) swap(f1,f2),swap(a,b); tmp = max(tmp , query(1,1,z,w[f1],w[a]) ); a = fa[f1],f1 = top[a]; } if(a == b) return tmp ; if(dep[a] > dep[b]) swap(a,b); return max(tmp , query(1,1,z,w[son[a]],w[b]) ); // 父边 } int main() { int root; int u,v,w1; int cas; scanf("%d",&cas); while(cas -- ) { scanf("%d",&n); cnt = 0 ; memset(head,-1,sizeof(head)); memset(tt,0,sizeof(tt)); for(int i = 1 ; i < n ; i ++ ) { scanf("%d%d%d",&u,&v,&w1); d1[i][0] = u; d1[i][1] = v; d1[i][2] = w1; add(u,v); add(v,u); } root = 1; dep[root] = 0 ; fa[root] = 0 ; dfs1(root); z = 0 ; dfs2(root,root); for(int i = 1 ; i < n ; i ++ ) { if(dep[d1[i][0]] > dep[d1[i][1]] ) swap(d1[i][0],d1[i][1]); update(1,1,z,w[d1[i][1]] ,d1[i][2]); } scanf("%s",str); while(str[0] != 'D') { scanf("%d%d",&u,&v); if(str[0] == 'Q') printf("%d ",find(u,v)); else update(1,1,z,w[d1[u][1]],v); scanf("%s",str); } } return 0; } /* tle 建树费时删去->tle // luangao -> tle 去掉自己宏定义的max和min -> AC!!!!!!!!!!!! */
据说这题还可用link_cut tree做，论文没看懂。。。
看这里 QTREE解法的一些研究
这类问题是动态树问题：算法合集之《动态树问题及其应用》 ，也没看懂。。。。