这是我的第一个边权链剖
COGS上和SPOJ有点不一样就是没有多组数据了本质还是一样的
我写的是COGS那个事实上改一改就能够去SPOJ AC了= -=
(但是我如今上不去SPOJ卧槽(╯‵□′)╯︵┻━┻)
【题目描写叙述】
一天机房的夜晚，无数人在MC里奋斗着。。。
大家都知道矿产对于MC来说是多么的重要。但因为矿越挖越少，勇士们不得不跑到更远的地方挖矿，但这样路途上就会花费相当大的时间。导致挖矿效率低下。
cjj提议修一条铁路。大家一致允许。
大家都被CH分配了一些任务：
zjmfrank2012负责绘制出一个矿道地图，这个地图包含家（当然这也是一个矿。毕竟不把家掏空我们是不会走的）。和无数个矿。所以大家应该能够想出这是一个无向无环图，也就是一棵树。
Digital_T和cstdio负责铺铁路。
。
所以这里没他们什么事。两位能够劳作去了。
这个时候song526210932和RMB突然发现有的矿道会刷怪，而且怪的数量会发生变化。作为採矿主力，他们想知道从一个矿到还有一个矿的路上哪一段会最困难。
。
。（困难值用zjm的死亡次数表示）。
【输入格式】
输入文件的第一行有一个整数N。代表矿的数量。矿的编号是1到N。
接下来N-1行每行有三个整数a,b,c。代表第i号矿和第j号矿之间有一条路。在初始时这条路的困难值为c。
接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值改动为ti，后者代表查询a到b所经过的道路中的最大困难值。
输入数据以一行“DONE”结束。
【输出格式】
对每一个“QUERY”操作，输出一行一个正整数，即最大困难值。
【例子输入】
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【例子输出】
1
3
【提示】
对于60%的数据。1
对于100%的数据。1
【来源】
由GDFRWMY 改编自SPOJ 375 QTREE
数据by cstdio
边权链剖略蛋疼
我用每条边两个端点里深度比較大的那个以点权继承这条边的边权
最后在Query_max函数在树的统计Count基础上略微改了改即可了
(直接暴力用LCA会出傻逼的错误我一開始居然没注意到多亏zky学长提醒QUQ)
//AC code by CreationAugust
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXINT 0x7fffffff
#define MAXN 100010
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
using namespace std;
int w;
int val[MAXN];
int size[MAXN],deep[MAXN],chain[MAXN],num[MAXN],fa[MAXN][18];
bool vis[MAXN];
int top,tp;
int a,b;
int u,v;
int n,T;
int x[MAXN],y[MAXN],z[MAXN];
char ch[6];
struct edge
{
edge *next;
int val;
int to;
}*prev[MAXN],e[MAXN*2];
struct seg
{
int maxn;
int l;
int r;
}tree[MAXN*4];
inline void insert(int u,int v,int w)
{
e[++top].to=v;
e[top].val=w;
e[top].next=prev[u];
prev[u]=&e[top];
}
inline void dfs1(int x)
{
size[x]=1;
vis[x]=1;
for (int i=1;i<=17;i++)
{
if (deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for (edge *i=prev[x];i;i=i->next)
{
int t=i->to;
if (vis[t]) continue;
deep[t]=deep[x]+1;
fa[t][0]=x;
dfs1(t);
size[x]+=size[t];
}
}
inline void dfs2(int x,int last)
{
chain[x]=last;
num[x]=++tp;
int t=0;
for (edge *i=prev[x];i;i=i->next)
if (deep[i->to]>deep[x]&&size[t]<size[i->to])
t=i->to;
if (!t) return;
dfs2(t,last);
for (edge *i=prev[x];i;i=i->next)
if (deep[i->to]>deep[x]&&i->to!=t)
dfs2(i->to,i->to);
}
inline void push_up(int rt)
{
tree[rt].maxn=max(tree[ln].maxn,tree[rn].maxn);
}
inline void build(int rt=1,int l=1,int r=n)
{
tree[rt].l=l;
tree[rt].r=r;
if (l==r) return;
int mid=(l+r)>>1;
build(lchild);
build(rchild);
}
inline int lca(int a,int b)
{
if (deep[a]<deep[b]) swap(a,b);
int t=deep[a]-deep[b];
for (int i=0;i<=17;i++)
if (t&(1<<i)) a=fa[a][i];
for (int i=17;i>=0;i--)
if (fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
if (a==b) return a;
else return fa[a][0];
}
void modify(int rt,int l,int r,int w)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (L==l&&r==R)
{
tree[rt].maxn=w;
return;
}
if (l>mid) modify(rn,l,r,w);
else
if (r<=mid) modify(ln,l,r,w);
else
{
modify(lchild,w);
modify(rchild,w);
}
push_up(rt);
}
void Modify(int a,int b,int w)
{
while (chain[a]!=chain[b])
{
modify(1,num[chain[a]],num[a],w);
a=fa[chain[a]][0];
}
modify(1,num[b],num[a],w);
}
inline int query_max(int rt,int l,int r)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (L==l&&R==r)
{
return tree[rt].maxn;
}
if (l>mid) return query_max(rn,l,r);
else
if (r<=mid) return query_max(ln,l,r);
else
return max(query_max(lchild),query_max(rchild));
}
inline int Query_max(int a,int b)
{
int ret=-MAXINT;
while (chain[a]!=chain[b])
{
ret=max(ret,query_max(1,num[chain[a]],num[a]));
a=fa[chain[a]][0];
}
if (num[b]+1<=num[a])
ret=max(ret,query_max(1,num[b]+1,num[a]));
return ret;
}
int main()
{
freopen("qtree.in","r",stdin);
freopen("qtree.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
insert(v,u,w);
x[i]=u;
y[i]=v;
z[i]=w;
}
dfs1(1);
dfs2(1,1);
build();
for (int i=1;i<n;i++)
{
if (deep[x[i]]<deep[y[i]])
val[y[i]]=z[i];
else
val[x[i]]=z[i];
}
for (int i=1;i<=n;i++)
modify(1,num[i],num[i],val[i]);
while (1)
{
scanf("%s",ch);
if (ch[1]=='H')
{
scanf("%d%d",&a,&b);
if (deep[x[a]]<deep[y[a]])
modify(1,num[y[a]],num[y[a]],b);
else
modify(1,num[x[a]],num[x[a]],b);
}
else
if (ch[1]=='U')
{
scanf("%d%d",&a,&b);
int t=lca(a,b);
printf("%d
",max(Query_max(a,t),Query_max(b,t)));
}
else
if (ch[1]=='O')
break;
}
}