题目描述如下
给出一棵有N个点的树,每个点都有一个值ai,两种操作:
1、U x y:修改第x个点的值为y;
2、Q x y:求第x个点到第y个点路径上所有点(包含x和y)的最大值
代码运行错误
//Include
#include<cstdio>
#include<cstring>
using namespace std;
//Basic
namespace Basic
{
template<typename Type>
inline Type Max(Type x,Type y)
{
if(x>y)return x;
else return y;
}
template<typename Type>
inline Type Min(Type x,Type y)
{
if(x<y)return x;
else return y;
}
template<typename Type>
inline void Swap(Type x,Type y)
{
Type tt=x;x=y;y=tt;
return ;
}
}
using namespace Basic;
//Const
//Type
namespace Tree
{
const int Maxn=210000;
#define ls(x) node[x].lc
#define rs(x) node[x].rc
struct _Segment_Tree_Node
{
int lc,rc,l,r,s;
};
struct _Segment_Tree
{
int len;
_Segment_Tree_Node node[Maxn*2];
_Segment_Tree(){Clean();}
inline void Clean(){len=0;}
inline void Build(int &now,int l,int r)
{
now=++len;
node[now].l=l;
node[now].r=r;
if(l==r)
{
return;
}
else
{
int m=(l+r)/2;
Build(ls(now),l, m );
Build(rs(now),m+1,r);
}
}
inline void Modify(int now,int pos,int val)
{
int l=node[now].l;
int r=node[now].r;
if(l==r)
{
node[now].s=val;
return ;
}
else
{
int m=(l+r)/2;
if(pos<=m)Modify(ls(now),pos,val);
else Modify(rs(now),pos,val);
node[now].s=Max(
node[ls(now)].s,
node[rs(now)].s);
}
}
inline int Query(int now,int L,int R)
{
int l=node[now].l;
int r=node[now].r;
if(L<=l&&r<=R)
{
return node[now].s;
}
else
{
int m=(l+r)/2;
if(m+1<=L) return Query(rs(now),L,R);
else if(m>=R)return Query(ls(now),L,R);
return Max(
Query(ls(now),L, m ),
Query(rs(now),m+1,R));
}
}
};
struct _Tree_Line
{
int x,y,next;
};
struct _Tree
{
int tot[Maxn],son[Maxn],dep[Maxn],dfn[Maxn],dad[Maxn],top[Maxn],root;
_Segment_Tree T;int len,last[Maxn];
_Tree_Line line[Maxn*2];
_Tree(){Clean();}
inline void Clean(){len=0;memset(last,-1,sizeof(last));}
inline void Insert(int x,int y)
{
line[len].x=x;line[len].y=y;
line[len].next=last[x];last[x]=len++;
}
inline void Dfs1(int x,int f)
{
dep[x]=dep[f]+1;
dad[x]=f;
son[x]=0;
tot[x]=1;
for(int k=last[x];k!=-1;k=line[k].next)
{
int y=line[k].y;
if(y==f)continue;
Dfs1(y,x);
if(tot[son[x]]<tot[y])son[x]=y;
tot[x]+=tot[y];
}
}
inline void Dfs2(int x,int t)
{
static int ts=0;ts++;
dfn[x]=ts;
top[x]=t;
if(son[x])
Dfs2(son[x],t);
else
return;
for(int k=last[x];k!=-1;k=line[k].next)
{
int y=line[k].y;
if(y==dad[x]||y==son[x])continue;
Dfs2(y,y);
}
}
inline int Solve(int x,int y)
{
int tx=top[x],ty=top[y],ans=0;
while(tx!=ty)
{
if(dep[tx]>dep[ty])
Swap(x,y),Swap(tx,ty);
ans=Max(ans,T.Query(root,dfn[ty],dfn[y]));
y=dad[ty];ty=top[y];
}
if(x==y)return Max(ans,T.Query(root,dfn[x],dfn[x]));
else
{
if(dep[x]>dep[y])Swap(x,y);
return Max(ans,T.Query(root,dfn[x],dfn[y]));
}
}
};
}
using namespace Tree;
//Define
_Tree T;
int n,m;
int arr[Maxn];
//Main
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
T.Insert(x,y);
T.Insert(y,x);
}
T.Dfs1(1,0);
T.Dfs2(1,1);
T.T.Build(T.root,1,n);
for(int i=1;i<=n;i++)T.T.Modify(T.root,T.dfn[i],arr[i]);
char st[3];
for(int i=1,x,y;i<=m;i++)
{
scanf("%s",st);
if(st[0]=='U')
{
scanf("%d%d",&x,&y);
T.T.Modify(T.root,T.dfn[x],y);
}
else
{
scanf("%d%d",&x,&y);
printf("%d\n",T.Solve(x,y));
}
}
return 0;
}
这题已经让我心态大崩一天了,恳请大佬相助,码风语法问题@我或自行百度