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][];
int z;
int n ;
char str[];
struct node
{
int v ,next;
}; node e[maxn * ];
int cnt ;
int head[maxn];
int tt[maxn * ]; 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*],tt[root*+]);
}
inline void dfs1(int u ) // 计算 sz[],son[],dep[],fa[];
{
sz[u] = ;
son[u] = ;
for(int i = head[u] ; i != - ; i = e[i].next)
if(e[i].v != fa[u])
{
fa[e[i].v] = u;
dep[e[i].v] = dep[u] + ;
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] != ) dfs2(son[u] , top[u]);
for(int i = head[u] ; i!= - ;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 ) / ;
if(pos <= mid)
update(root + root ,l,mid, pos , val);
else
update(root + root + ,mid + , 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 ) / ;
int res = ;
if(l <= mid )
res = max(res , query(root + root,l1 , mid , l , r ));
if(r > mid )
res = max(res , query(root + root + ,mid + , r1 , l , r ));
return res;
}
int find(int a,int b)
{
int f1 = top[a] , f2 = top[b] , tmp = ;
while( f1 != f2 )
{
if(dep[f1] < dep[f2])
swap(f1,f2),swap(a,b);
tmp = max(tmp , query(,,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(,,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 = ;
memset(head,-,sizeof(head));
memset(tt,,sizeof(tt));
for(int i = ; i < n ; i ++ )
{
scanf("%d%d%d",&u,&v,&w1);
d1[i][] = u;
d1[i][] = v;
d1[i][] = w1;
add(u,v);
add(v,u);
}
root = ;
dep[root] = ;
fa[root] = ;
dfs1(root);
z = ;
dfs2(root,root);
for(int i = ; i < n ; i ++ )
{
if(dep[d1[i][]] > dep[d1[i][]] ) swap(d1[i][],d1[i][]);
update(,,z,w[d1[i][]] ,d1[i][]);
}
scanf("%s",str);
while(str[] != 'D')
{
scanf("%d%d",&u,&v);
if(str[] == 'Q')
printf("%d\n",find(u,v));
else update(,,z,w[d1[u][]],v);
scanf("%s",str);
}
}
return ;
}
/*
tle
建树费时删去->tle
// luangao -> tle
去掉自己宏定义的max和min -> AC!!!!!!!!!!!!
*/
据说这题还可用link_cut tree做，论文没看懂。。。
看这里 QTREE解法的一些研究
这类问题是动态树问题：算法合集之《动态树问题及其应用》 ，也没看懂。。。。