A.
考虑把(u,v)的询问离线挂在u上，然后dfs，每次从fath[x]到[x]相当于x子树dis区间加1，x子树以外区间-1，然后维护区间和区间平方和等。
常数略大。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxv 100500
#define maxe 200500
using namespace std;
long long n,fath[maxv],q,uu,vv,dis[maxv],l[maxv],r[maxv],times=,fdfn[maxv],g[maxv],nume=,ans[maxv],cnt;
long long tot=,root,ls[maxv<<],rs[maxv<<],val1[maxv<<],val2[maxv<<],lazy[maxv<<];
vector <long long> v[maxv],id[maxv];
bool vis[maxv];
struct edge
{
long long v,nxt;
}e[maxe];
long long read()
{
char ch;long long data=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data;
}
void addedge(long long u,long long v)
{
e[++nume].v=v;e[nume].nxt=g[u];g[u]=nume;
e[++nume].v=u;e[nume].nxt=g[v];g[v]=nume;
}
void pushup(long long now,long long left,long long right)
{
val1[now]=val1[ls[now]]+val1[rs[now]];
val2[now]=val2[ls[now]]+val2[rs[now]];
}
void pushdown(long long now,long long left,long long right)
{
if (!lazy[now]) return;
long long mid=left+right>>,d=lazy[now],ll=mid-left+,rr=right-mid;
val1[ls[now]]+=*d*val2[ls[now]]+d*d*ll;val1[rs[now]]+=*d*val2[rs[now]]+d*d*rr;
val2[ls[now]]+=d*ll;val2[rs[now]]+=d*rr;
lazy[ls[now]]+=d;lazy[rs[now]]+=d;
lazy[now]=;
}
void build(long long &now,long long left,long long right)
{
now=++tot;lazy[now]=;
if (left==right)
{
val1[now]=dis[fdfn[left]]*dis[fdfn[left]];val2[now]=dis[fdfn[left]];
return;
}
long long mid=left+right>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
pushup(now,left,right);
}
long long ask(long long now,long long left,long long right,long long l,long long r)
{
pushdown(now,left,right);
if ((left==l) && (right==r)) return val1[now];
long long mid=left+right>>;
if (r<=mid) return ask(ls[now],left,mid,l,r);
else if (l>=mid+) return ask(rs[now],mid+,right,l,r);
else return ask(ls[now],left,mid,l,mid)+ask(rs[now],mid+,right,mid+,r);
}
void modify(long long now,long long left,long long right,long long l,long long r,long long val)
{
if (l>r) return;
pushdown(now,left,right);
if ((left==l) && (right==r))
{
lazy[now]+=val;
val1[now]+=*val*val2[now]+val*val*(right-left+);val2[now]+=val*(right-left+);
return;
}
long long mid=left+right>>;
if (r<=mid) modify(ls[now],left,mid,l,r,val);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,val);
else
{
modify(ls[now],left,mid,l,mid,val);
modify(rs[now],mid+,right,mid+,r,val);
}
pushup(now,left,right);
}
void get_ans(long long x)
{
for (long long i=;i<v[x].size();i++)
ans[id[x][i]]=ask(root,,n,l[v[x][i]],r[v[x][i]]);
}
void modify_tree(long long x,long long f)
{
modify(root,,n,l[x],r[x],-f);
modify(root,,n,,l[x]-,f);
modify(root,,n,r[x]+,n,f);
}
void dfs1(long long x)
{
l[x]=r[x]=++times;fdfn[times]=x;
for (long long i=g[x];i;i=e[i].nxt)
{
long long v=e[i].v;
if (v!=fath[x])
{
dis[v]=dis[x]+;
dfs1(v);
r[x]=max(r[x],r[v]);
}
}
}
void dfs2(long long x)
{
get_ans(x);
for (long long i=g[x];i;i=e[i].nxt)
{
long long v=e[i].v;
if (v!=fath[x])
{
modify_tree(v,);
dfs2(v);
modify_tree(v,-);
}
}
}
int main()
{
n=read();
for (long long i=;i<=n-;i++) {fath[i+]=read();addedge(fath[i+],i+);}
q=read();
for (long long i=;i<=q;i++)
{
uu=read();vv=read();
v[uu].push_back(vv);id[uu].push_back(i);
}
dfs1();build(root,,n);
dfs2();
for (long long i=;i<=q;i++) printf("%lld\n",ans[i]);
return ;
}
B.
我们发现k=0的时候可以o(1)计算（毕竟是01序列）。当k>=1的时候可以证明答案是ceil(l/2)*trunc(l/2)。
要善于猜结论啊。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500500
using namespace std;
long long n,q,a[maxn],s1[maxn],s[maxn],x[maxn],y[maxn],k[maxn],cnt[][maxn],ans[maxn],tab[maxn];
long long read()
{
char ch;long long data=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data;
}
void calc(long long type,long long pos)
{
cnt[][]=;tab[]=;
for (long long i=;i<=n;i++)
{
cnt[][i]=cnt[][i-];cnt[][i]=cnt[][i-];
if (!s[i]) cnt[][i]++;
else cnt[][i]++;
tab[i]=tab[i-]+cnt[s[i]^][i];
}
if (!type)
{
for (long long i=;i<=n;i++)
{
if (x[i]>=) ans[i]=(cnt[][y[i]-]-cnt[][x[i]-])*cnt[][y[i]]+(cnt[][y[i]-]-cnt[][x[i]-])*cnt[][y[i]]-(tab[y[i]-]-tab[x[i]-]);
else ans[i]=cnt[][y[i]-]*cnt[][y[i]]+cnt[][y[i]-]*cnt[][y[i]]-tab[y[i]-];
}
}
}
int main()
{
n=read();q=read();
for (long long i=;i<=n;i++) {a[i]=read();s1[i]=s1[i-]^a[i];s[i]=s1[i];}
for (long long i=;i<=q;i++) {x[i]=read();y[i]=read();k[i]=read();x[i]++;y[i]++;}
calc(,);
for (int i=;i<=q;i++)
{
if (k[i])
{
long long l=y[i]-x[i]+;
ans[i]=(l/+(l&))*(l/);
}
}
for (long long i=;i<=q;i++) printf("%lld\n",ans[i]);
return ;
}
C.
这TM的是个环套树啊。、
我们找出路径上的值，然后每次加gcd(环长，m）加到最大即可。
之前10分的原因是神TM没开long long。（我就说我怎么可能写挂这种题）（撤回）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 100500
#define maxe 200500
using namespace std;
struct edge
{
long long v,w,nxt;
}e[maxe];
long long n,g[maxv],nume=,dis1[maxv],dis2[maxv],root,father[maxv],anc[maxv][],dep[maxv];
long long r1,r2,q,s,t,m,u,v,w,a,b,x;
long long read()
{
char ch;long long data=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data;
}
void addedge(long long u,long long v,long long w) {e[++nume].v=v;e[nume].w=w;e[nume].nxt=g[u];g[u]=nume;}
long long getfather(long long x)
{
if (x!=father[x]) father[x]=getfather(father[x]);
return father[x];
}
bool unionn(long long a,long long b)
{
long long f1=getfather(a),f2=getfather(b);
if (f1==f2) return true;
father[f1]=f2;return false;
}
void dfs(long long x,long long father)
{
for (long long i=g[x];i;i=e[i].nxt)
{
long long v=e[i].v;
if (v!=father)
{
anc[v][]=x;dep[v]=dep[x]+;
dis1[v]=dis1[x]+e[i].w;dis2[v]=dis2[x]+e[i^].w;
dfs(v,x);
}
}
}
void get_table()
{
for (long long e=;e<=;e++)
for (long long i=;i<=n;i++)
anc[i][e]=anc[anc[i][e-]][e-];
}
long long lca(long long x,long long y)
{
if (dep[x]<dep[y]) swap(x,y);
for (long long e=;e>=;e--)
if ((dep[anc[x][e]]>=dep[y]) && (anc[x][e]))
x=anc[x][e];
if (x==y) return x;
for (long long e=;e>=;e--)
{
if (anc[x][e]!=anc[y][e])
{
x=anc[x][e];
y=anc[y][e];
}
}
return anc[x][];
}
long long gcd(long long a,long long b)
{
if (!b) return a;
return gcd(b,a%b);
}
long long calc(long long x)
{
x=(x%m+m)%m;
long long f1=(r1%m+m)%m,d1=gcd(f1,m);
return (m--x)/d1*d1+x;
}
int main()
{
n=read();
for (long long i=;i<=n;i++) father[i]=i;
for (long long i=;i<=n;i++)
{
a=read();b=read();x=read();
if (unionn(a,b)) {root=a;u=a;v=b;w=x;}
else {addedge(a,b,x);addedge(b,a,-x);}
}
dfs(root,);get_table();
r1=dis1[v]-w;r2=dis2[v]+w;
q=read();
for (long long i=;i<=q;i++)
{
s=read();t=read();m=read();x=lca(s,t);
printf("%lld\n",calc(dis2[s]-dis2[x]+dis1[t]-dis1[x]));
}
return ;
}