有点难度的树链刨分
这道题 想到解法很简单关键是写的时候比较ex 至少我写了1个多小时才写完还有颇多的细节处理。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。树刨之后线段树维护颜色这个很好维护因为我们都写过线段树维护的区间最大连续子段和。
然后 维护一下区间修改一下 然后 查询一下即可。 关键是查询好吧。
对于查询我们显然 是边求LCA边查询然后边统计答案 对于l r这种答案必须得特殊处理一下 考虑 我们l r不管是在左边还是右边只要是合理的拼接就可以成功 然后 对于l 我们想一下这是线段树上的 我们要把查询出来的结果翻转显然 观察你的线段树和你所画的图即可。
r的话可以不用翻转也是观察图 最后合并即可。
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define lv(x) t[x].lv #define rv(x) t[x].rv #define tag(x) t[x].tag #define INF 2147483646 #define tn ver[i] using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return; } const int MAXN=100002; int n,m,len,cnt; int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1]; int f[MAXN],top[MAXN],son[MAXN],d[MAXN],a[MAXN]; int sz[MAXN],id[MAXN],ans[MAXN],pos[MAXN]; char b[2]; struct wy { int l,r; int sum; int lv,rv,tag; wy(){lv=rv=tag=sum=l=r=0;} }t[MAXN<<2]; void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void dfs(int x,int father) { d[x]=d[father]+1; sz[x]=1;f[x]=father; for(int i=lin[x];i;i=nex[i]) { if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[tn]>sz[son[x]])son[x]=tn; } } inline void dp(int x,int father) { id[x]=++cnt;pos[cnt]=a[x]; top[x]=father; if(!son[x])return; dp(son[x],father); for(int i=lin[x];i;i=nex[i]) if(tn!=f[x]&&tn!=son[x])dp(tn,tn); return; } inline void build(int p,int l,int r) { l(p)=l;r(p)=r; if(l==r){lv(p)=rv(p)=pos[l];sum(p)=1;return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); sum(p)=sum(p<<1)+sum(p<<1|1)-((rv(p<<1)==lv(p<<1|1))?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); return; } inline void pushdown(int p) { sum(p<<1)=sum(p<<1|1)=1; lv(p<<1)=rv(p<<1)=lv(p<<1|1)=rv(p<<1|1)=tag(p); tag(p<<1)=tag(p<<1|1)=tag(p); tag(p)=0;return; } inline wy ask(int p,int l,int r) { if(l<=l(p)&&r>=r(p))return t[p]; int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); wy a,b; if(l<=mid)a=ask(p<<1,l,r); if(r>mid)b=ask(p<<1|1,l,r); sum(p)=sum(p<<1)+sum(p<<1|1)-(rv(p<<1)==lv(p<<1|1)?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); if(!a.sum)return b; if(!b.sum)return a; a.sum=a.sum+b.sum-(a.rv==b.lv?1:0); a.rv=b.rv; return a; } inline int Task(int x,int y) { int fx=top[x],fy=top[y]; wy l,r,tmp;//l代表x r代表y while(fx!=fy) { if(d[fx]>d[fy]) { tmp=ask(1,id[fx],id[x]); swap(tmp.lv,tmp.rv); x=f[fx];fx=top[x]; if(!l.sum){l=tmp;continue;} l.sum=l.sum+tmp.sum-(l.rv==tmp.lv?1:0); l.rv=tmp.rv; } else { tmp=ask(1,id[fy],id[y]); y=f[fy];fy=top[y]; if(!r.sum){r=tmp;continue;} r.sum=r.sum+tmp.sum-(r.lv==tmp.rv?1:0); r.lv=tmp.lv; } } if(id[x]>id[y]) { tmp=ask(1,id[y],id[x]); swap(tmp.lv,tmp.rv); if(!l.sum)l=tmp; else { l.sum=l.sum+tmp.sum-(l.rv==tmp.lv?1:0); l.rv=tmp.rv; } } else { tmp=ask(1,id[x],id[y]); if(!r.sum)r=tmp; else { r.sum=r.sum+tmp.sum-(r.lv==tmp.rv?1:0); r.lv=tmp.lv; } } tmp.sum=l.sum+r.sum-(l.rv==r.lv?1:0); return tmp.sum; } inline void change(int p,int l,int r,int k) { if(l<=l(p)&&r>=r(p)) { tag(p)=k;sum(p)=1; lv(p)=rv(p)=k; return; } int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); sum(p)=sum(p<<1)+sum(p<<1|1)-(rv(p<<1)==lv(p<<1|1)?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); return; } inline void Tchange(int x,int y,int z) { int fx=top[x],fy=top[y]; while(fx!=fy) { if(d[fx]<d[fy])swap(fx,fy),swap(x,y); change(1,id[fx],id[x],z); x=f[fx];fx=top[x]; } if(id[x]<id[y])swap(x,y); change(1,id[y],id[x],z); return; } int main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0);dp(1,1); build(1,1,cnt); for(int i=1;i<=m;++i) { int x,y,z; scanf("%s",b+1); x=read();y=read(); if(b[1]=='Q')put(Task(x,y)); else z=read(),Tchange(x,y,z); } return 0; }View Code
下面是今天对拍所用文件 对拍真的爽。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<map> #include<stack> #include<set> #include<bitset> #include<cstdlib> using namespace std; int main() { for(int t=1;t<=100000;t++) { system("E:\\random.exe"); double st=clock(); system("E:\\bf.exe"); double ed=clock(); system("E:\\sol.exe"); if(system("fc E:\\2.out E:\\1.out")) { puts("Wrong Answer"); return 0; } else { printf("Accepted,测试点 #%d,用时 %.0lfms\n",t,ed-st); } } return 0; }pai
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<map> #include<stack> #include<set> #include<bitset> #include<cstdlib> using namespace std; int n,m; int a[1000]; int f[1000],cnt; int getfather(int x){return x==f[x]?x:f[x]=getfather(f[x]);} int main() { freopen("1.in","w",stdout); srand(time(0)); n=rand()%5+2; m=rand()%5+1; cout<<n<<' '<<m<<endl; for(int i=1;i<=n;++i)cout<<rand()%n+1<<' '; cout<<endl; for(int i=1;i<=n;++i)f[i]=i; while(cnt<n-1) { int x=rand()%n+1; int y=rand()%n+1; int xx=getfather(x); int yy=getfather(y); if(xx==yy)continue; f[xx]=yy;++cnt; cout<<x<<' '<<y<<endl; } for(int i=1;i<=m;++i) { if(i&1) { cout<<"Q"<<endl; int l=rand()%n+1; int r=rand()%n+1; cout<<l<<' '<<r<<' '<<endl; } else { cout<<"C"<<endl; int l=rand()%n+1; int r=rand()%n+1; int z=rand()%1000000000+1; cout<<l<<' '<<r<<' '<<z<<endl; } } return 0; }random
没有思考好细节下次一定要想好。
可能心有点乱了 必须回去学习文化课的决定已经下好了 。我一定会对自己负责的。也第一定不会自己辜负自己的。
就算是为了自己吧。看我神威 无坚不摧！
这道题是一个树链刨分但我手滑了好几次 比如dp写成dfs 没有push up 还有long long 没有搞全。
关于long long这个问题 我想是应该计算一下空间如果空间足够那全部都开long long不够的话那就只能局部开了 把所有有可能爆long long的地方全开上，不然wa了可就难受 退役了。不开longlong见祖宗啊。
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define tag(x) t[x].tag #define INF 2147483646 #define ll long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(ll x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return; } const int MAXN=100002; int n,m,cnt,len; int a[MAXN],pos[MAXN],id[MAXN],f[MAXN]; int top[MAXN],d[MAXN],son[MAXN],sz[MAXN]; int lin[MAXN<<1],ver[MAXN<<1],nex[MAXN<<1]; struct wy { int l,r; ll sum; ll tag; }t[MAXN<<2]; inline void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void dfs(int x,int father) { f[x]=father;sz[x]=1; d[x]=d[father]+1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[son[x]]<sz[tn])son[x]=tn; } return; } inline void dp(int x,int father) { top[x]=father; id[x]=++cnt; pos[cnt]=a[x]; if(!son[x])return; dp(son[x],father); for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn!=f[x]&&tn!=son[x]) dp(tn,tn); } return; } inline void build(int p,int l,int r) { l(p)=l;r(p)=r; if(l==r){sum(p)=pos[l];return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); sum(p)=sum(p<<1)+sum(p<<1|1); } inline void pushdown(int p) { ll mid=(l(p)+r(p))>>1; tag(p<<1)+=tag(p); tag(p<<1|1)+=tag(p); sum(p<<1)+=(mid-l(p)+1)*tag(p); sum(p<<1|1)+=(r(p)-mid)*tag(p); tag(p)=0;return; } inline void change(int p,int l,int r,ll k) { if(l<=l(p)&&r>=r(p)) { tag(p)+=k; sum(p)+=(r(p)-l(p)+1)*k; return; } int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); sum(p)=sum(p<<1)+sum(p<<1|1); return; } inline ll ask(int p,int l,int r) { if(l<=l(p)&&r>=r(p))return sum(p); ll cnt=0; int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)cnt+=ask(p<<1,l,r); if(r>mid)cnt+=ask(p<<1|1,l,r); sum(p)=sum(p<<1)+sum(p<<1|1); return cnt; } inline ll Task(int x,int y) { int fx=top[x];int fy=top[y]; ll ans=0; while(fx!=fy) { ans+=ask(1,id[fx],id[x]); x=f[fx];fx=top[x]; } ans+=ask(1,id[y],id[x]); return ans; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0);dp(1,1); build(1,1,cnt); for(int i=1;i<=n;++i) { int p,x,y; p=read(); switch(p) { case 1:x=read();y=read(); change(1,id[x],id[x],y); break; case 2:x=read();y=read(); change(1,id[x],id[x]+sz[x]-1,y); break; case 3:x=read(); put(Task(x,1)); break; } } return 0; }View Code
值得一提的是这个问题可以使用线段树直接解决 我指的是单指这道题。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define c(x) t[x].add #define v(x) t[x].k using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(long long x) { x<0?putchar('-'),x=-x:0; long long num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(10);return; } const long long MAXN=200002; struct wy1{long long l,r;}s[MAXN]; struct wy { long long l,r,sum; long long k;//k表示属性 long long add; }t[MAXN<<2]; long long n,m; long long lin[MAXN],ver[MAXN],nex[MAXN],len=0; long long cnt,a[MAXN],b[MAXN],vis[MAXN]; void add(long long x,long long y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } void dfs(long long x,long long father) { s[x].l=++cnt;vis[cnt]=1; for(long long i=lin[x];i;i=nex[i]) { long long tn=ver[i]; if(tn==father)continue; dfs(tn,x); } s[x].r=++cnt; } void build(long long p,long long l,long long r) { l(p)=l;r(p)=r; if(l==r){if(vis[l])v(p)=1;else v(p)=-1;return;} long long mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); v(p)=v(p<<1)+v(p<<1|1); return; } void pushdown(long long p) { sum(p<<1)+=v(p<<1)*c(p); sum(p<<1|1)+=v(p<<1|1)*c(p); c(p<<1)+=c(p); c(p<<1|1)+=c(p); c(p)=0;return; } void change(long long p,long long l,long long r,long long d) { if(l<=l(p)&&r>=r(p)) { c(p)+=d; sum(p)+=v(p)*d; return; } if(c(p))pushdown(p); long long mid=(l(p)+r(p))>>1; if(l<=mid)change(p<<1,l,r,d); if(r>mid)change(p<<1|1,l,r,d); sum(p)=sum(p<<1)+sum(p<<1|1); return; } long long ask(long long p,long long l,long long r) { if(l<=l(p)&&r>=r(p))return sum(p); if(c(p))pushdown(p); long long cnt=0; long long mid=(l(p)+r(p))>>1; if(l<=mid)cnt+=ask(p<<1,l,r); if(r>mid)cnt+=ask(p<<1|1,l,r); return cnt; } int main() { //freopen("1.in","r",stdin); int __size__ = 20 << 20; // 20MB char *__p__ = (char*)malloc(__size__) + __size__; __asm__("movl %0, %%esp\n" :: "r"(__p__)); n=read();m=read(); for(long long i=1;i<=n;i++)a[i]=read(); for(long long i=1;i<n;i++) { long long x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0); //for(long long i=1;i<=n;i++)cout<<i<<' '<<s[i].v<<' '<<s[i].l<<' '<<s[i].r<<endl; build(1,1,cnt); for(int i=1;i<=n;i++) { change(1,s[i].l,s[i].l,a[i]); change(1,s[i].r,s[i].r,a[i]); } for(long long i=1;i<=m;i++) { long long p,x,d; p=read(); if(p==1) { x=read();d=read(); change(1,s[x].l,s[x].l,d); change(1,s[x].r,s[x].r,d); } if(p==2) { x=read();d=read(); change(1,s[x].l,s[x].r,d); } if(p==3) { x=read(); put(ask(1,1,s[x].l)); } } return 0; }View Code
以前写的这道题 运用的是dfs序的变形刚好能解决这道题 mlogn 比树刨快。
这道题就有意思的很了，我不太会写 不过这种难度的题目 应该难不倒我。。
考虑换根之后 的询问分三种情况 x==root 直接就是线段树上的所有点的最小值。
1 我们原本定义根的时候 root在x的外部也就是说非x的子树 那么就很显然了这肯定是在x的上部 如果由他为根向下扫的话x的子树还是他的子树直接查询x的子树即可 。
2 重点是 root在x的内部 也就是说除了x到root这条路不能走以外其他的都是可以走的所以此时 把这条不能走的路径抛掉就是能走的 （因为这条路径是连续的）直接 跑即可。在我没有A这道题前是没有这两个结论的一直很迷 对拍了一下才恍然大悟 样例真不愧是脚做的。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<map> #include<stack> #include<set> #include<bitset> #include<cstdlib> using namespace std; int n,m; int a[1000]; int f[1000],cnt; int getfather(int x){return x==f[x]?x:f[x]=getfather(f[x]);} int main() { freopen("1.in","w",stdout); srand(time(0)); n=rand()%5+2; m=rand()%10+1; cout<<n<<' '<<m<<endl; for(int i=1;i<=n;++i)f[i]=i; while(cnt<n-1) { int x=rand()%n+1; int y=rand()%n+1; int xx=getfather(x); int yy=getfather(y); if(xx==yy)continue; f[xx]=yy;++cnt; cout<<x<<' '<<y<<endl; } for(int i=1;i<=n;++i)cout<<rand()%n+1<<' '; cout<<endl; cout<<rand()%n+1<<endl; for(int i=1;i<=m;++i) { if(i%3+1==1) { cout<<1<<endl; cout<<rand()%n+1<<endl; } if(i%3+1==2) { cout<<2<<endl; int l=rand()%n+1,r=rand()%n+1; cout<<l<<' '<<r<<' '<<rand()%n+1<<endl; } if(i%3+1==3) { cout<<3<<endl; cout<<rand()%n+1<<endl; } } return 0; }random
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define tag(x) t[x].tag #define INF 214748364682ll #define ll long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(ll x) { x<0?putchar('-'),x=-x:0; ll num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return; } const ll MAXN=100002; ll n,m,cnt,len,root,w; ll a[MAXN],pos[MAXN]; ll id[MAXN],f[MAXN]; ll top[MAXN],d[MAXN],son[MAXN],sz[MAXN]; ll lin[MAXN<<1],ver[MAXN<<1],nex[MAXN<<1]; struct wy { ll l,r; ll sum; ll tag; }t[MAXN<<2]; inline ll min(ll x,ll y){return x>y?y:x;} inline void add(ll x,ll y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void dfs(ll x,ll father) { f[x]=father;sz[x]=1; d[x]=d[father]+1; for(ll i=lin[x];i;i=nex[i]) { ll tn=ver[i]; if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[son[x]]<sz[tn])son[x]=tn; } return; } inline void dp(ll x,ll father) { top[x]=father; id[x]=++cnt; pos[cnt]=a[x]; if(!son[x])return; dp(son[x],father); for(ll i=lin[x];i;i=nex[i]) { ll tn=ver[i]; if(tn!=f[x]&&tn!=son[x])dp(tn,tn); } return; } inline void build(ll p,ll l,ll r) { l(p)=l;r(p)=r; if(l==r){sum(p)=pos[l];return;} ll mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); sum(p)=min(sum(p<<1),sum(p<<1|1)); } inline void pushdown(ll p) { tag(p<<1)=tag(p<<1|1)=tag(p); sum(p<<1)=sum(p<<1|1)=tag(p); tag(p)=0;return; } inline void change(ll p,ll l,ll r,ll k) { if(l<=l(p)&&r>=r(p)) { tag(p)=sum(p)=k; return; } ll mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); sum(p)=min(sum(p<<1),sum(p<<1|1)); return; } inline ll ask(ll p,ll l,ll r) { if(l<=l(p)&&r>=r(p))return sum(p); ll cnt=INF; ll mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)cnt=min(cnt,ask(p<<1,l,r)); if(r>mid)cnt=min(cnt,ask(p<<1|1,l,r)); sum(p)=min(sum(p<<1),sum(p<<1|1)); return cnt; } inline void Tchange(ll x,ll y,ll z) { ll fx=top[x],fy=top[y]; while(fx!=fy) { if(d[fx]<d[fy])swap(x,y),swap(fx,fy); change(1,id[fx],id[x],z); x=f[fx];fx=top[x]; } if(d[x]<d[y])swap(x,y); change(1,id[y],id[x],z); return; } inline ll Task(ll x,ll y) { if(x==y)return sum(1); ll ans=INF,last; ll fx=top[x],fy=top[y],z=x; while(fx!=fy) { if(d[fx]<d[fy])last=fy,y=f[fy],fy=top[y]; else x=f[fx],fx=top[x]; } if(y!=x)last=son[x]; if(d[x]<d[y])swap(x,y); if(y!=z)ans=min(ans,ask(1,id[z],id[z]+sz[z]-1)); else { ll l=id[last],r=id[last]+sz[last]-1; if(1<=l-1)ans=min(ans,ask(1,1,l-1)); if(r+1<=cnt)ans=min(ans,ask(1,r+1,cnt)); } return ans; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(ll i=1;i<n;++i) { ll x,y; x=read();y=read(); add(x,y);add(y,x); } for(ll i=1;i<=n;++i)a[i]=read(); w=root=read(); dfs(root,0);dp(root,root); build(1,1,cnt); for(ll i=1;i<=m;++i) { ll p,x,y,z; p=read(); switch(p) { case 1:root=read(); break; case 2:x=read();y=read(); z=read();Tchange(x,y,z); break; case 3:x=read();put(Task(x,root)); break; } } return 0; }View Code
当然 具体细节自然是得自己思考的啦。
我是真服我自己了 这么简单的题目 都提交了三次 原因是 线段树空间开小了 还有就是 一个id[x] 写成x 无脑wa
我是个SB 以后如果这种简单的题目还不能一遍AC的话 我是不会原谅自己的。
那说一下这道题目的做法 一个点的祖先显然是他到根的路径上的所有点 一直爬到根节点怎么样 这样显然是树刨一直跳。即可 线段树中维护当前这条链中被标记的元素的最大标号即可。复杂度nlog^2n一直慢慢的往上跳 直到寻找到一个有值的且最大的就是答案了。
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define w(x) t[x].w #define INF 2147483646 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return; } const int MAXN=100002; int n,m,len,cnt; int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1]; int f[MAXN],top[MAXN],son[MAXN],d[MAXN]; int sz[MAXN],id[MAXN],ans[MAXN],pos[MAXN]; char a[2]; struct wy { int l,r; int w; }t[MAXN<<2]; inline void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline int max(int x,int y){return x>y?x:y;} inline void dfs(int x,int father) { f[x]=father;sz[x]=1; d[x]=d[father]+1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[son[x]]<sz[tn])son[x]=tn; } return; } inline void dp(int x,int father) { top[x]=father; id[x]=++cnt;pos[cnt]=x; if(!son[x])return; dp(son[x],father); for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn!=f[x]&&tn!=son[x])dp(tn,tn); } return; } inline void build(int p,int l,int r) { l(p)=l;r(p)=r; if(l==r){if(l==1)w(p)=l;return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); w(p)=max(w(p<<1),w(p<<1|1)); } inline int ask(int p,int l,int r) { if(l<=l(p)&&r>=r(p))return w(p); int cnt=0; int mid=(l(p)+r(p))>>1; if(l<=mid)cnt=max(cnt,ask(p<<1,l,r)); if(r>mid)cnt=max(cnt,ask(p<<1|1,l,r)); return cnt; } inline void change(int p,int l,int r) { if(l<=l(p)&&r>=(r(p))) { w(p)=l; return; } int mid=(l(p)+r(p))>>1; if(l<=mid)change(p<<1,l,r); if(r>mid)change(p<<1|1,l,r); w(p)=max(w(p<<1),w(p<<1|1)); return; } inline int Task(int x) { int fx=top[x]; int ans=0; while(fx!=1) { ans=ask(1,id[fx],id[x]); x=f[fx];fx=top[x]; if(ans)return ans; } if(ans)return ans; ans=ask(1,id[fx],id[x]); return ans; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0);dp(1,1); build(1,1,cnt); for(int i=1;i<=m;++i) { int x; scanf("%s",a+1); x=read(); if(a[1]=='Q')put(pos[Task(x)]); else change(1,id[x],id[x]); } return 0; }View Code
值得一提的是 我这种做法完全是没有必要的。线段树直接就可以解决。对于标记点我们标记它的整颗子树查询时单点查询 只需要知道他有没有被标记过即可 复杂度nlogn 真是学习过了高级的数据结构放下了普通数据结构的应用了这点很不应该。
更多精彩
