Cap1taL @ 2022-08-03 19:15:28
只WA了一个点
代码
// Problem: P3038 [USACO11DEC]Grass Planting G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3038
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define MAXM 100003
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define ford(a,b,c) for(int a=b;a>=c;a--)
#define RT return 0;
#define db(x) cout<<endl<<x<<endl;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
inline void out(LXF x){
if(x<0){
x=-x;
putchar('-');
}
if(x>9) out(x/10);
putchar(x%10+'0');
}
int n,m,a[MAXN],id[MAXN],dep[MAXN],top[MAXN],fa[MAXN],siz[MAXN],son[MAXN],cnt,ecnt,head[MAXN];
struct E{
int v,nxt;
}e[MAXM<<1];
void add_e(int u,int v){
e[++ecnt]=(E){v,head[u]};
head[u]=ecnt;
}
void dfs1(int s,int fath){
fa[s]=fath;
siz[s]=1;
dep[s]=dep[fath]+1;
int maxson=-1;
for(int i=head[s];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fath){
dfs1(v,s);
siz[s]+=siz[v];
if(siz[v]>maxson){
maxson=siz[v];
son[s]=v;
}
}
}
}
void dfs2(int s,int topf){
id[s]=++cnt;
top[s]=topf;
if(!son[s]) return ;
dfs2(son[s],topf);
for(int i=head[s];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[s]&&v!=son[s]){
dfs2(v,v);
}
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
return y;
}
//SegTree
struct Segtree{
int l,r,sum,lz;
}tr[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return 1+(x<<1);}
void push_up(int p){
tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
}
void update(int p,int k){
tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
tr[p].lz+=k;
}
void push_down(int p){
update(lc(p),tr[p].lz);
update(rc(p),tr[p].lz);
tr[p].lz=0;
}
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(lc(p),l,mid);
build(rc(p),mid+1,r);
push_up(p);
}
void modify(int p,int nl,int nr,int k){
int l=tr[p].l,r=tr[p].r;
if(r<nl||nr<l) return ;
if(nl<=l&&r<=nr){
update(p,k);
return ;
}
push_down(p);
modify(lc(p),nl,nr,k);
modify(rc(p),nl,nr,k);
push_up(p);
}
int qurey(int p,int nl,int nr){
int l=tr[p].l,r=tr[p].r;
if(r<nl||nr<l) return 0;
if(nl<=l&&r<=nr) return tr[p].sum;
push_down(p);
return qurey(lc(p),nl,nr)+qurey(rc(p),nl,nr);
}
void updRange(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
// printf("modify(1,%d,%d,%d)\n",id[top[x]],id[x],k);
modify(1,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
// printf("modify(1,%d,%d,%d)\n",id[y],id[x],k);
modify(1,id[y],id[x],k);
}
int main(){
n=RIN,m=RIN;
foru(i,1,n-1){
int u=RIN,v=RIN;
add_e(u,v);
add_e(v,u);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(m--){
char op;
scanf("%c",&op);
int x=RIN,y=RIN;
if(op=='P'){
updRange(x,y,1);
int lca=LCA(x,y);
updRange(lca,lca,-1);
}else{
printf("%d\n",qurey(1,id[(dep[x]>dep[y]?x:y)],id[(dep[x]>dep[y]?x:y)]));
}
}
return 0;
}
RIN是快读,见上方define,a=RIN相当于a=read()
最后那个地方如果改成cin>>op>>x>>y就AC了
如果按代码里的写,那个测试点尽管只有一个Q,会输出很多次0
测试点如下:
in
7 7
3 1
3 2
3 4
3 5
3 6
3 7
P 1 2
P 4 2
P 5 2
P 6 2
P 3 2
P 7 2
Q 3 2
out
6
by yqyx @ 2022-08-03 19:39:01
scanf("%c",&op);
会读入回车。
by xieyikai2333 @ 2022-08-03 19:48:00
@XHZS_XY 切记,读入字符时要
scanf(" %c",&op);
^
这个空格千万不能少!!!
by Cap1taL @ 2022-08-03 21:18:13
@xieyikai2333 谢谢各位dalao