【题目大意】
给定一棵树，然后给出两种操作：
1、改变某条边的权值
2、询问点x到点y的路径上，长度最长的边的长度是多少？
【算法分析】
我是按照漆子超大神的论文做的。
他如是说道：
对于一棵树，定义Size(u)为以u为根的子树的结点数。
然后对于u与所有儿子v相连的边而言，Size(v)最大的，那条边就叫重边，其它边都是轻边。
Then，有一个重要结论：
每个点到根的路径上都不超过O(lg N)条轻边和O(lg N)条重路径。
（重路径是由重边连续连成的）
然后我们对于每个询问(x,y)的路径，就可以分成(x,lca(x,y))的路径和(y,lca(x,y))的路径。
于是问题变成怎么求x到它一个祖先结点的边权的最大值。
我们就可以轻边直接算，重路径利用线段树求解。
最终就可以在O(Q lg ^2 n)的复杂度得到解。(Q问询问个数)
至于具体实现的话，我是把连续的重边先DFS，然后再DFS其它轻边。
弄一个队列装起来，这样DFS完以后就可以保证连续的重边(重路径)在队列里是连续的。
然后就把连续的重路径涂上同一个颜色。在记录一下这种颜色在队里里起始点是哪。
方便后面利用。
至于求lca我是利用的经典的转化为RMQ求解。
当然，少不了N个指向数组指来指去。。。。
，指到头都晕了。
【用到的东西】
LCA——>RMQ
线段树
【其它】
我那叫一个激动啊。。200+行，5KB的程序一次过样例，一次AC！
3552963 2010-04-24 18:16:42 cwj Query on a tree accepted 4.25 6.0M
C++
4.0.0-8
时间有点丑，大概是因为我每次都memset的关系吧。。。
不过能A就成。。。
【CODE】
#include
#define min(x,y) (x)<(y)?(x):(y)
const int E=20005;
const int N=10005;
const int INF=1000000000;
struct edge{int x,y,w,next,op,heavy,inlist;}g[E];
struct Node{int l,r,data;}tr[E*5];
int n,Tc,e,heavytot,ctot,rmqtot,ans,nowdep;
int ls[N],Size[N],dep[N],fa[N];
int heavyedge[N],color[E],colorst[E];
int R[E],rmq[16][E],lg[E];
inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}
void addedge(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w;
g[e].next=ls[x]; ls[x]=e;
}
void init(){
e=0;
heavytot=0;
ctot=0;
rmqtot=0;
memset(ls,0,sizeof(ls));
memset(heavyedge,0,sizeof(heavyedge));
memset(Size,0,sizeof(Size));
memset(g,0,sizeof(g));
memset(fa,0,sizeof(fa));
memset(color,0,sizeof(color));
memset(colorst,0,sizeof(colorst));
memset(R,0,sizeof(R));
memset(rmq,0,sizeof(rmq));
char op[100];
int x,y,w,i;
scanf("%d",&n);
for (i=1;i
addedge(x,y,w);
g[e].op=i+n-1;
}
for (i=1;i
g[e].op=i;
}
}
void Get_Size(int p,int ×){
rmq[0][++rmqtot]=dep[p];
R[p]=rmqtot;
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
Get_Size(g[t].y,times);
rmq[0][++rmqtot]=dep[p];
}
Size[p]=times-Size[p];
}
void Get_heavyedge(int p){
int zz=0,mm=0;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && Size[g[t].y]>mm){
mm=Size[g[t].y];
zz=t;
}
if (!zz) return;
heavyedge[++heavytot]=zz;
g[zz].heavy=1;
g[zz].inlist=heavytot;
g[g[zz].op].heavy=1;
g[g[zz].op].inlist=heavytot;
Get_heavyedge(g[zz].y);
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && t!=zz)
Get_heavyedge(g[t].y);
}
void draw_color(){
ctot=1; color[heavyedge[1]]=1; colorst[1]=1;
for (int i=2;i<=heavytot;i++){
int &t=heavyedge[i],&pt=heavyedge[i-1];
if (g[pt].y!=g[t].x){
ctot++;
colorst[ctot]=i;
}
color[t]=ctot;
color[g[t].op]=ctot;
}
}
void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r;
if (l==r){
tr[p].data=g[heavyedge[l]].w;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}
void buildrmq(){
int i,k;
lg[1]=0;
for (i=2;i<=rmqtot;i++){
lg[i]=lg[i-1];
if (1<
for (k=1;(1<
void pre_work(){
int tmp=0;
dep[1]=1;
fa[1]=0;
Get_Size(1,tmp);
Get_heavyedge(1);
draw_color();
build(1,1,heavytot);
buildrmq();
}
void Change(int p,int pos){
if (tr[p].l==tr[p].r){
tr[p].data=g[heavyedge[pos]].w;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (pos<=mid) Change(p*2,pos);
else Change(p*2+1,pos);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}
int getmin(int x,int y){
if (x>y) swap(x,y);
int step=lg[y-x+1];
return min(rmq[step][x],rmq[step][y-(1<
int getmax(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r) return tr[p].data;
int tmp1=-INF,tmp2=-INF,mid=(tr[p].l+tr[p].r)/2;
if (l<=mid) tmp1=getmax(p*2,l,r);
if (r>=mid+1) tmp2=getmax(p*2+1,l,r);
return max(tmp1,tmp2);
}
void Try(int x){
if (dep[x]==nowdep) return;
if (g[fa[x]].heavy){
int &p=g[heavyedge[colorst[color[fa[x]]]]].x,tmp;
if (dep[p]>=nowdep){
Try(p);
tmp=getmax(1,colorst[color[fa[x]]],g[fa[x]].inlist);
ans=max(ans,tmp);
}
else{
tmp=getmax(1,g[fa[x]].inlist-(dep[x]-nowdep-1),g[fa[x]].inlist);
ans=max(ans,tmp);
}
}
else{
Try(g[fa[x]].x);
ans=max(ans,g[fa[x]].w);
}
}
void solve(){
char op[100];
int x,y;
for (;;){
scanf("%s",op+1);
if (op[1]==’D’) return;
if (op[1]==’C’){
scanf("%d%d",&x,&y);
g[x].w=y;
g[g[x].op].w=y;
if (g[x].heavy) Change(1,g[x].inlist);
}
else{
ans=0;
scanf("%d%d",&x,&y);
nowdep=getmin(R[x],R[y]);
Try(x);
Try(y);
printf("%dn",ans);
}
}
}
int main(){
scanf("%d",&Tc);
for (int i=0;i
pre_work();
solve();
}
}