【NOIP模拟】精灵

精灵"/>

【NOIP模拟】精灵

题面

wonderland的地图可以抽象成一个N个点的有根树，第i个点上生活着编号为i的精灵，根节点为1号节点。
一个点的深度定义为这个节点到根的距离+1，第i只精灵和第j只精灵的亲密度为他们在树上最近公共祖先的深度。
现在Jessica想询问你Q次，每次询问第z只精灵和第l~r只精灵的亲密度的和是多少。答案对201314（不是一个质数）取模。
第一行有2个整数，分别代表N,Q。
接下来N-1行，分别表示点2到点N的父亲节点编号。
接下来Q行，每行3个整数，分别代表一组询问的l r z。
输出共Q行，每行一个整数表示询问的答案，答案对201314（不是一个质数）取模。

对于所有数据：N,Q≤10^5, 1≤l≤r≤N, 1≤z≤N。
Subtask1(5分):Q,N≤5
Subtask2(10分):Q≤100,N≤500
Subtask3(15分):Q≤1000,N≤1000
Subtask4(15分):树的形态为一条链，x(x≥2)节点的父亲为x-1。
Subtask5(30分):z为定值
Subtask6(25分):无特殊限

分析

我只会暴力！！正解只会思路，但是目前还没调出来qvq，最后会附上传送门。

这个题难度被简化了，因为数据弱了，但是很符合noip的感觉，就是特殊数据不少，用来练练暴力是不错的

我觉得我的暴力不算优秀，敲了100分钟，近200行，期望得分75，实际得分60，挂了longlong！！【仰头长叹

 首先 有30分的 N²：我是直接跑的lca，就对于[l,r]区间内每个点，直接与z求lca

15分的 一条链 ：而且这条链连顺序都是定的，就直接算。比如z深度较浅，z就永远是lca，就（r-l+1）*dep[z]，类似的，共三种情况，讨论就行了。

还有30分的z是定值：可以差分，但是我懒得想那么多了，就摆了颗线段树，写着也挺快的，就查询和建树俩操作

其实正解看这题5min就想出来了，奈何树剖敲不熟。不过这个题数据真的好温柔qvq

最后分享这个特殊数据 大家练练暴力啊qvq(一共20组 两部分)：Part1 Part2

正解树链剖分传送门

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 201314
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (t[p].l+t[p].r>>1) 
#define N 100100
#define ll long long
ll n,m,u,cnt,seg=1,line=1,orgz;
ll lm[N],rm[N],zm[N],out[N],son[N],dep[N],first[N];
ll fa[N][20];
ll ans,tmp,a[N];
inline void read(ll &x)
{x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}struct email
{ll u,v;ll nxt;
}e[N*4];
struct tree
{ll l,r;ll sum;
}t[N*4];
inline void add(ll u,ll v)
{e[++cnt].nxt=first[u];first[u]=cnt;e[cnt].u=u;e[cnt].v=v;
}void dfs(ll u,ll f)
{for(ll i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];for(ll i=first[u];i;i=e[i].nxt){ll v=e[i].v;if(v==f)continue;dep[v]=dep[u]+1;fa[v][0]=u;dfs(v,u);}
}inline ll lca(ll x,ll y)
{if(dep[x]<dep[y])swap(x,y);ll t=dep[x]-dep[y];for(ll i=0;(1<<i)<=t;i++)if(t&(1<<i))x=fa[x][i];if(x==y)return x;for(ll i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}inline void pushup(ll p)
{t[p].sum=t[lc].sum+t[rc].sum;
}inline void build(ll p,ll l,ll r)
{t[p].l=l;t[p].r=r;if(l==r){t[p].sum=a[l];return ;}ll bm=l+r>>1;build(lc,l,bm);build(rc,bm+1,r);pushup(p);
}inline ll query(ll p,ll ql,ll qr)
{ll ret=0;if(ql<=t[p].l&&qr>=t[p].r)return t[p].sum;if(ql<=mid){tmp=query(lc,ql,qr);ret=(ret%mod+tmp%mod)%mod;}if(qr>mid){tmp=query(rc,ql,qr);ret=(ret%mod+tmp%mod)%mod;}return ret;
}void work_seg()
{for(ll i=1;i<=n;i++)a[i]=dep[lca(orgz,i)];build(1,1,n);for(ll i=1;i<=m;i++){ans=0;ll l,r;l=lm[i],r=rm[i];tmp=query(1,l,r);ans=(ans%mod+tmp%mod)%mod;printf("%lld\n",ans);}
}void work_line()
{for(ll i=1;i<=n;i++)dep[i]=i;for(ll i=1;i<=m;i++){ans=0;ll l,r,z;l=lm[i],r=rm[i],z=zm[i];if(dep[l]<=dep[z]&&dep[r]<=dep[z]){tmp=(dep[l]+dep[r])*(abs(r-l)+1)/2;ans=(ans%mod+tmp%mod)%mod;}if(dep[l]>=dep[z]&&dep[r]>=dep[z]){tmp=dep[z]*(abs(r-l)+1);ans=(ans%mod+tmp%mod)%mod;}if(dep[l]<dep[z]&&dep[r]>dep[z]){tmp=(dep[l]+dep[z])*(abs(l-z)+1)/2+dep[z]*abs(r-z);ans=(ans%mod+tmp%mod)%mod;}printf("%lld\n",ans);}
}void work()
{for(ll i=1;i<=m;i++){ans=0;ll l,r,z;l=lm[i],r=rm[i],z=zm[i];if(l>r)swap(l,r);for(ll j=l;j<=r;j++)ans=(ans%mod+dep[lca(z,j)]%mod)%mod;printf("%lld\n",ans);}
}int main()
{scanf("%d%d",&n,&m);for(ll v=2;v<=n;v++){read(u);add(u,v);add(v,u);out[u]++;son[u]=v;}for(ll i=1;i<=m;i++){read(lm[i]),read(rm[i]),read(zm[i]);    if(i==1)orgz=zm[i];if(zm[i]!=orgz)seg=0;}for(ll i=1;i<n;i++){if(out[i]==1&&son[i]==i+1)continue;else{line=0;break;}}    if(out[n]!=0)line=0;if(line){work_line();return 0;} dfs(1,0);for(ll i=1;i<=n;i++)dep[i]++;if(seg){work_seg();return 0;}if(n<=2000){work();return 0;}            
}

转载于:.html