P3038这道题 我用下面这段代码可以通过
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,cnt,idx;
int head[N],dep[N],son[N],top[N],siz[N],fa[N],id[N],a[N];
struct edge
{
int next,to;
}e[N<<1];
struct segment_tree
{
int l,r,val,laz_tag;
}t[N<<2];
inline void add_edge(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void push_up(int x)
{
t[x].val=t[x<<1].val+t[x<<1|1].val;
}
inline void push_down(int x)
{
if(!t[x].laz_tag) return;
t[x<<1].laz_tag+=t[x].laz_tag;
t[x<<1|1].laz_tag+=t[x].laz_tag;
t[x<<1].val+=(t[x<<1].r-t[x<<1].l+1)*t[x].laz_tag;
t[x<<1|1].val+=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].laz_tag;
t[x].laz_tag=0;
}
inline void build(int l,int r,int x)
{
t[x].l=l;
t[x].r=r;
if(l==r)
{
t[x].val=a[l];
return;
}
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
push_up(x);
}
inline void update(int nl,int nr,int k,int l,int r,int x)
{
if(nl<=l&&r<=nr)
{
t[x].val+=(r-l+1)*k;
t[x].laz_tag+=k;
return;
}
push_down(x);
int mid=l+r>>1;
if(nl<=mid) update(nl,nr,k,l,mid,x<<1);
if(nr>mid) update(nl,nr,k,mid+1,r,x<<1|1);
push_up(x);
}
inline int query(int nl,int nr,int l,int r,int x)
{
if(nl<=l&&r<=nr)
{
return t[x].val;
}
push_down(x);
int mid=l+r>>1,res=0;
if(nl<=mid) res+=query(nl,nr,l,mid,x<<1);
if(nr>mid) res+=query(nl,nr,mid+1,r,x<<1|1);
return res;
}
inline void dfs1(int u,int fath)
{
dep[u]=dep[fath]+1;
fa[u]=fath;
siz[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fath) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
inline void dfs2(int u,int fst)
{
id[u]=++idx;
top[u]=fst;
if(!son[u]) return;
dfs2(son[u],fst);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline void trlist_update(int u,int v,int w)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(id[top[u]],id[u],w,1,n,1);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(id[u]+1,id[v],w,1,n,1);
}
inline int trlist_query(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=query(id[top[u]],id[u],1,n,1);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=query(id[u]+1,id[v],1,n,1);
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
while(m--)
{
char op;
cin>>op;
if(op=='P')
{
int u,v;
scanf("%d%d",&u,&v);
trlist_update(u,v,1);
}
if(op=='Q')
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",trlist_query(u,v));
}
}
return 0;
}
但是如果把cin>>op改成scanf("%c",&op)就会re
是我的scanf打错了吗,我字符串一般不用scanf,用scanf输入字符串有什么注意事项吗