题解 P4114 【Qtree1】
这算是一道树链剖分模板题，但是从维护点权改成了维护边权
宣传一波博客
如果不会树链剖分的话请先学习树链剖分
题解正式开始
这道题的一个难点就是如何维护边权，那肯定要将将边权转化成点权才行。
我们考虑一条边，它一定连接父亲节点和儿子节点（这不肯定的吗……），如果用父亲节点来存的话，该节点的其他儿子的边就没法存，但如果用儿子节点来存的话就没有这种问题（一个节点可以有多个儿子，但不会有超过一个的父亲），这样，将边权值存在哪的问题就解决了。
那怎么存呢？我们考虑一下，存点权的树链剖分是在第二遍DFS的时候处理点权的，因此，我们可以记录从当前节点到它的父节点的边权作为它的点权。
第二遍DFS的代码如下：
inline void did2(long long u,long long topf,long long l1)//l1代表该节点到父亲节点的距离。
{
id[u]=++cnt;
w[cnt]=l1;//这就是记录边权了
top[u]=topf;
if (!son[u]) return;
long long lx;//因为要先找重儿子，所以提前求出该节点到重儿子的距离
for (long long i=he[u];i;i=ne[i]) if (to[i]==son[u]) lx=ll[i];
did2(son[u],topf,lx);
for (register long long i=he[u];i;i=ne[i])
{
register long long v=to[i];
if (v==f[u]||v==son[u]) continue;
did2(v,v,ll[i]);//ll数组记录路径长，这就是儿子节点到该节点的距离了
}
}不要以为这就完事了，当我们要求值时，原本的代码如下：
inline long long quimax(long long x,long long y)
{
register long long ans=0;
while(top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+qui(1,id[top[x]],id[x]));
x=f[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=(ans+qui(1,id[x],id[y]));
return ans;
}有没有发现有什么问题？
我们发现，最后这一段
ans=(ans+qui(1,id[x],id[y]));中，我们求的其实是f[x]到y的路径的边权和，而不是x到y的路径的边权和，我们考虑到x，y在一条重链上，所以求son[x]，y就相当于求x，y的值了。
正确代码如下：
inline long long quimax(long long x,long long y)
{
register long long ans=-1e11;
while(top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,qui(1,id[top[x]],id[x]));
x=f[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=max(ans,qui(1,id[son[x]],id[y]));//求x到y的路径的边权和。
return ans;
}这道题还有一个问题就是如何找出存储第x条边的节点
这就要利用链式前向星的一点性质了
对于一个有向图，第x条边所指向的节点就是to[x]（bian[x].to），而对于无向图的话，第x条边所连接的节点就是to[2 x]和to[2 x-1] (bian[2 s].to和bian[2 x-1].to,这个依据个人习惯)，而这两个节点中深的那个节点就是儿子节点了（因为深度[儿子]=深度[父亲]+1啊……)，然后修改这个节点就行了……
其他的就和树链剖分的代码一样了……总代码如下，和模板树链剖分一样的和上文解释过的，就不加注释了……（累死了）
#include<bits/stdc++.h>
using namespace std;
long long qq,n,m,r1,p,q,i,k,x,y,cnt,top[1000001],w[1000001],a[1000001],dep[1000001],f[1000001],siz[1000001],he[1000001],ll[2000001],ne[2000001],to[2000001],z[4000001],l[4000001],r[4000001],c[4000001],son[1000001],id[1000001];
inline void did1(long long u,long long fat,long long dee)
{
dep[u]=dee;
f[u]=fat;
siz[u]=1;
register long long max1=-1;
register long long v;
for (register long long i=he[u];i;i=ne[i])
{
v=to[i];
if (v==fat) continue;
did1(v,u,dee+1);
if (siz[v]>max1)
{
son[u]=v;
max1=siz[v];
}
siz[u]+=siz[v];
}
}
inline void did2(long long u,long long topf,long long l1)
{
id[u]=++cnt;
w[cnt]=l1;
top[u]=topf;
if (!son[u]) return;
long long lx;
for (long long i=he[u];i;i=ne[i]) if (to[i]==son[u]) lx=ll[i];
did2(son[u],topf,lx);
for (register long long i=he[u];i;i=ne[i])
{
register long long v=to[i];
if (v==f[u]||v==son[u]) continue;
did2(v,v,ll[i]);
}
}
inline void build(long long u,long long l1,long long r1)
{
l[u]=l1;
r[u]=r1;
if (l1==r1)
{
z[u]=w[l1];
return;
}
build(u*2,l1,(l1+r1)/2);
build(u*2+1,(l1+r1)/2+1,r1);
z[u]=max(z[u*2],z[u*2+1]);
}
inline void jia(long long u,long long l1,long long r1,long long k)
{
if ((l[u]>r1)||(r[u]<l1)) return;
if ((l[u]>=l1)&&(r[u]<=r1))
{
z[u]=k;
return;
}
jia(u*2,l1,r1,k);
jia(u*2+1,l1,r1,k);
z[u]=max(z[u*2],z[u*2+1]);
}
inline long long qui(long long u,long long l1,long long r1)
{
if ((l1>r[u])||(r1<l[u])) return -1e11;
if ((l1<=l[u])&&(r1>=r[u])) return z[u];
return max(qui(u*2,l1,r1),qui(u*2+1,l1,r1));
}
inline long long quimax(long long x,long long y)
{
register long long ans=-1e11;
while(top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,qui(1,id[top[x]],id[x]));
x=f[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=max(ans,qui(1,id[son[x]],id[y]));
return ans;
}
int main()
{
scanf("%lld",&n);
for (i=1;i<n;i++)
{
scanf("%lld%lld%lld",&x,&y,&r1);//链式前向星
cnt++;
ne[cnt]=he[x];
to[cnt]=y;
ll[cnt]=r1;
he[x]=cnt;
cnt++;
ne[cnt]=he[y];
to[cnt]=x;
ll[cnt]=r1;
he[y]=cnt;
}
did1(1,0,1);
cnt=0;
did2(1,1,0);//个人习惯1节点到0节点距离为0……实际上啥都可以。
build(1,1,n);
q=getchar();
while(q<'A'||q>'Z') q=getchar();
qq=getchar();
while (qq>='A'&&qq<='Z') qq=getchar();//千万不要用cin，太慢了，作者喜欢用getchar()；
while(q!='D')
{
scanf("%lld%lld",&x,&y);
if (q=='Q')
if (x!=y)
printf("%lld\n",quimax(x,y));
else
printf("0\n");
else
{
r1=to[2*x];
p=to[2*x-1];//找出这条边所连的两个节点
if (dep[r1]>dep[p]) jia(1,id[r1],id[r1],y);
else jia(1,id[p],id[p],y);//找出儿子节点，进行修改
}
q=getchar();
while(q<'A'||q>'Z') q=getchar();
qq=getchar();
while(qq>='A'&&qq<='Z') qq=getchar();
}
return 0；
}这道题就完事了