思路：
裸裸的树链剖分....
树链剖分就是把一棵树分成若干重链和轻链...然后保证形成的线段树上每条链是连续存储的。然后这样就能用线段树进行维护了。
但是每次一定要保证是在同一条链里边....思路就是这样....
感觉最近越来越淡定了，题目卡住了也不怎么着急了，慢慢看代码...嗯...有点像学习的感觉了....
明天青岛理工的邀请赛要好好玩玩...
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int myw[];
bool vis[];
int siz[],dep[],top[],fa[],son[],w[],fp[];
int totw;
char typ[];
long long INF=0x3f3f3f3f3f;
struct edge
{
int id;
edge *next;
};
edge edges[<<];
edge *adj[];
struct tr
{
int s,e,maxx;
long long sum;
};
tr tree[<<];
void build(int k,int s,int e)
{
tree[k].s=s;
tree[k].e=e;
if(s==e)
{
tree[k].sum=tree[k].maxx=myw[fp[s]];
return;
}
int mid=(s+e)>>;
build(k<<,s,mid);
build(k<<|,mid+,e);
tree[k].maxx=max(tree[k<<].maxx,tree[k<<|].maxx);
tree[k].sum=tree[k<<|].sum+tree[k<<].sum;
}
int ednum;
inline void AddEdge(int a,int b)
{
edge *tmp;
tmp=&edges[ednum++];
tmp->id=b;
tmp->next=adj[a];
adj[a]=tmp;
} void dfs1(int id,int mdep,int f)
{
vis[id]=;
dep[id]=mdep;
siz[id]=;
fa[id]=f;
son[id]=;
int tmpsiz=-;
for(edge *it=adj[id]; it; it=it->next)
{
if(!vis[it->id])
{
dfs1(it->id,mdep+,id);
if(tmpsiz<siz[it->id])
{
tmpsiz=siz[it->id];
son[id]=it->id;
}
siz[id]+=siz[it->id];
}
}
}
void dfs2(int id,int ase)
{
vis[id]=;
top[id]=ase;
w[id]=++totw;
fp[totw]=id;
if(son[id])
dfs2(son[id],ase);
for(edge *it=adj[id]; it; it=it->next)
{
if(!vis[it->id])
{
dfs2(it->id,it->id);
}
}
}
long long ans;
void querySum(int k,int s,int e)
{
if(tree[k].e==e&&tree[k].s==s)
{
ans+=tree[k].sum;
return;
}
int mid=(tree[k].s+tree[k].e)>>;
if(e<=mid)
{
querySum(k<<,s,e);
}
else if(s>mid)
{
querySum(k<<|,s,e);
}
else
{
querySum(k<<,s,mid);
querySum(k<<|,mid+,e);
}
}
void qsum(int a,int b)
{
int f1=top[a],f2=top[b]; ans=;
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(a,b);
}
querySum(,w[f1],w[a]);
a=fa[f1];
f1=top[a];
}
if(dep[a]>dep[b])
swap(a,b);
querySum(,w[a],w[b]);
printf("%lld\n",ans);
}
void queryMax(int k,int s,int e)
{
if(tree[k].e==e&&tree[k].s==s)
{
ans=max(ans,(long long)tree[k].maxx);
return;
}
int mid=(tree[k].s+tree[k].e)>>;
if(e<=mid)
{
queryMax(k<<,s,e);
}
else if(s>mid)
{
queryMax(k<<|,s,e);
}
else
{
queryMax(k<<,s,mid);
queryMax(k<<|,mid+,e);
}
}
void qmax(int a,int b)
{
int f1=top[a],f2=top[b];
ans=INF*(-);
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(a,b);
}
queryMax(,w[f1],w[a]);
a=fa[f1];
f1=top[a];
}
if(dep[a]>dep[b])
swap(a,b);
queryMax(,w[a],w[b]);
printf("%lld\n",ans);
}
void update(int k,int pos,int val)
{
if(tree[k].s==tree[k].e)
{
tree[k].sum=tree[k].maxx=val;
return;
}
int mid=(tree[k].s+tree[k].e)>>;
if(pos<=mid)
update(k<<,pos,val);
else
update(k<<|,pos,val);
tree[k].sum=tree[k<<|].sum+tree[k<<].sum;
tree[k].maxx=max(tree[k<<].maxx,tree[k<<|].maxx);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(siz,,sizeof(siz));
memset(vis,,sizeof(vis));
memset(son,,sizeof(son));
fa[]=;
totw=;
ednum=;
for(int i=;i<=n;i++)
{
adj[i]=NULL;
}
for(int i=; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
AddEdge(a,b);
AddEdge(b,a);
}
for(int i=; i<=n; i++)
{
scanf("%d",&myw[i]);
}
dfs1(,,);
memset(vis,,sizeof(vis));
dfs2(,);
build(,,totw);
scanf("%d",&m);
for(int i=; i<=m; i++)
{
int a,b;
scanf("%s%d%d",typ,&a,&b);
if(typ[]=='X')
{
qmax(a,b);
}
else if(typ[]=='M')
{
qsum(a,b);
}
else if((typ[]=='N'))
{
update(,w[a],b);
}
}
}
}
/*
8
1 2
1 4
2 3
3 8
5 6
7 5
2 5
3 7 6 5 8 2 1 0
1000
*/