3626: [LNOI2014]LCA

链剖。。。题解看hz的。。。。离线搞

1 #include
      
         2 #define lowbit(a) ((a)&(-(a)))  3 #define l(a) ((a)<<1)  4 #define r(a) ((a)<<1|1)  5 #define clr(a,x) memset(a,x,sizeof(a))  6 #define rep(i,l,r) for(int i=l;i<(r);i++)  7 #define Rep(i,a) rep(i,0,e[a].size())  8 typedef long long ll;  9 using namespace std; 10 int read() 11 { 12     char c=getchar(); 13     int ans=0,f=1; 14     while(!isdigit(c)){ 15         if(c=='-') f=-1; 16         c=getchar(); 17     } 18     while(isdigit(c)){ 19         ans=ans*10+c-'0'; 20         c=getchar(); 21     } 22     return ans*f; 23 } 24 struct node{ 25     int l,r,sum,add; 26 }; 27 struct query{ 28     int x,p; 29     bool f; 30     inline bool operator<(const query&A)const{ 31         return x
       

e[maxn]; 39 void dfs(int k){ 40 size[k]=1; 41 Rep(i,k){ 42 int to=e[k][i]; 43 if(to==f[k]) continue; 44 f[to]=k; 45 dep[to]=dep[k]+1; 46 dfs(to); 47 size[k]+=size[to]; 48 if(!son[k]||size[son[k]]

>1; 76 build(l(k),l,mid); 77 build(r(k),mid+1,r); 78 maintain(k); 79 } 80 void modify(int k,int l,int r,int t){ 81 pushdown(k); 82 if(x[k].l==l&&x[k].r==r){ 83 x[k].sum+=(r-l+1)*t; 84 x[k].add+=t; 85 return; 86 } 87 int mid=(x[k].l+x[k].r)>>1; 88 if(r<=mid) modify(l(k),l,r,t); 89 else if(l>mid) modify(r(k),l,r,t); 90 else{ 91 modify(l(k),l,mid,t); 92 modify(r(k),mid+1,r,t); 93 } 94 maintain(k); 95 } 96 int find(int k,int l,int r){ 97 pushdown(k); 98 if(x[k].l==l&&x[k].r==r) return x[k].sum; 99 int mid=(x[k].l+x[k].r)>>1;100 if(r<=mid) return find(l(k),l,r);101 if(l>mid) return find(r(k),l,r);102 return (find(l(k),l,mid)+find(r(k),mid+1,r));103 }104 void add(int u,int v,int t){105 while(top[u]!=top[v]){106 if(dep[top[u]]

dep[v]) swap(u,v);111 modify(1,id[u],id[v],t);112 }113 int sum(int u,int v){114 int ans=0;115 while(top[u]!=top[v]){116 if(dep[top[u]]

dep[v]) swap(u,v);121 ans+=find(1,id[u],id[v]);122 return ans%mod;123 }124 void init(){125 dep[0]=1;126 dfs(0);127 Dfs(Top=0);128 build(1,1,n);129 }130 int main()131 { 132 n=read(),m=read();133 rep(i,1,n){134 int to=read();135 e[to].push_back(i);136 e[i].push_back(to);137 }138 init();139 int cnt=0;140 rep(i,0,m){141 int l=read(),r=read();g[i]=read();142 q[cnt].x=l-1;q[cnt].p=i;q[cnt++].f=0;143 q[cnt].x=r;q[cnt].p=i;q[cnt++].f=1;144 }145 m<<=1;146 sort(q,q+m);147 cnt=-1;148 rep(i,0,m){149 while(cnt

>1) printf("%d\n",(ans[i]+mod)%mod);157 return 0;158 }