救!!!不知道哪里写错了。。。
查看原帖
救!!!不知道哪里写错了。。。
225862
LINK_LJM楼主2020/6/14 16:22
#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL,int>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=5e4+5;
const int inf=0x3f3f3f3f;
const int MOD=201314;
struct node{
    int nm,z,id;
    bool f;
    bool operator < (const node &ls)const {
        return nm<ls.nm;
    }
}p[maxn<<1];
struct TMD{
    int to,next;
}edge[maxn<<1];
int head[maxn],cnt,knt,n,m,deep[maxn],f[maxn],ans[maxn];
int top[maxn],sz[maxn],sn[maxn],tree[maxn],pre[maxn];
int sum[maxn<<2],lazy[maxn<<2];

void add(int from,int to){
    edge[++cnt]={to,head[from]};
    head[from]=cnt;
}
void dfs1(int now,int fa){
    deep[now]=deep[fa]+1;
    sz[now]=1;f[now]=fa;
    for(int i=head[now];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to,now);
        sz[now]+=sz[to];
        if(!sn[now]||sz[sn[now]]<sz[to]) sn[now]=to;
    }
}
void dfs2(int now,int fa,int tp){
    tree[now]=++knt;pre[knt]=now;top[now]=tp;
    if(!sn[now]) return ;
    dfs2(sn[now],now,tp);
    for(int i=head[now];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==fa||to==sn[now]) continue;
        dfs2(to,now,to);
    }
}
void pushdown(int l,int r,int rt){
    int mid=(l+r)>>1;
    if(lazy[rt]){
        lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%MOD;
        lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%MOD;
        sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(mid-l+1)%MOD)%MOD;
        sum[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt]*(r-mid)%MOD)%MOD;
        lazy[rt]=0;
    }
}
void modify(int L,int R,int l,int r,int rt,int k){
    if(L<=l&&R>=r){
        lazy[rt]=(lazy[rt]+k)%MOD;
        sum[rt]=(sum[rt]+(r-l+1)*k)%MOD;return ;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid) modify(L,R,l,mid,rt<<1,k);
    if(R>mid) modify(L,R,mid+1,r,rt<<1|1,k);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void get_modify(int x,int y){
    int f1=top[x],f2=top[y];
    while(f1!=f2){
        if(deep[f1]<deep[f2]) swap(f1,f2),swap(x,y);
        modify(tree[f1],tree[x],1,n,1,1);
        x=f[f1],f1=top[x];
    }
    if(deep[x]<deep[y]) swap(x,y);
    modify(tree[y],tree[x],1,n,1,1);
}
int dfs_sum(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r) return sum[rt];
    pushdown(l,r,rt);
    int mid=(l+r)>>1,ant=0;
    if(L<=mid) ant=(ant+dfs_sum(L,R,l,mid,rt<<1))%MOD;
    if(R>mid) ant=(ant+dfs_sum(L,R,mid+1,r,rt<<1|1))%MOD;
    return ant;
}
int get_sum(int x,int y){
    int f1=top[x],f2=top[y];
    int ant=0;
    while(f1!=f2){
        if(deep[f1]<deep[f2]) swap(f1,f2),swap(x,y);
        ant=(ant+dfs_sum(tree[f1],tree[x],1,n,1))%MOD;
        x=f[f1],f1=top[x];
    }
    if(deep[x]<deep[y]) swap(x,y);
    ant=(ant+dfs_sum(tree[y],tree[x],1,n,1))%MOD;
    return ant;
}
int main(){
    int u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++){
        scanf("%d",&u);++u;
        add(u,i);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        ++u;++v;++w;
        p[2*i-1]={u-1,w,i,false};
        p[2*i]={v,w,i,true};
    }
    sort(p+1,p+2*m+1);
    dfs1(1,0);
    dfs2(1,0,1);
    int id=1;
    for(int i=1;i<=2*m;i++){
        while(id<=p[i].nm) get_modify(1,id++);
        if(p[i].f){
            ans[p[i].id]=(ans[p[i].id]+get_sum(1,p[i].z)+MOD)%MOD;
        }else{
            ans[p[i].id]-=get_sum(1,p[i].z);
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}
2020/6/14 16:22
加载中...