题目大意：给定1棵树，每一个点有1个色彩，屡次询问色彩在
没记错的话这题我知道的有3种解法来着？
(茴香豆的茴有4种写法泥萌知道嘛…?
1.线段树保护虚树
2.点分治+线段树
3.分块
第1种方法我不知道在线怎样弄= = (我其实不知道怎样在虚树上进行点定位
第3种方法貌似内存过不去？
因而果断点分治+线段树
写完发现内存还是炸了= =
后来发现既然保护的是和不是最值那还要线段树干吗= =
直接开个vector保护前缀和直接2分不就行了= =
时间复杂度
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 150100
#define B 400
using namespace std;
typedef vector<pair<int,long long> > abcd;
int n,m,A;
int a[M];
long long last_ans;
namespace Tree{
struct edge{
int to,f,next;
bool ban;
}table[M<<1];
int head[M],tot=1;
int dpt[M],pos[M],T;
int log_2[M<<1],min_dpt[M<<1][18];
void Add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x,int from)
{
int i;
min_dpt[pos[x]=++T][0]=dpt[x];
for(i=head[x];i;i=table[i].next)
if(table[i].to!=from)
{
dpt[table[i].to]=dpt[x]+table[i].f;
DFS(table[i].to,x);
min_dpt[++T][0]=dpt[x];
}
}
void Build_LCA()
{
int i,j;
for(i=2;i<=T;i++)
log_2[i]=log_2[i>>1]+1;
for(j=1;j<=log_2[T];j++)
for(i=1;i+(1<<j)-1<=T;i++)
min_dpt[i][j]=min(min_dpt[i][j-1],min_dpt[i+(1<<j-1)][j-1]);
}
long long LCA_Depth(int x,int y)
{
x=pos[x];y=pos[y];
if(x>y) swap(x,y);
int l=log_2[y-x+1];
return min(min_dpt[x][l],min_dpt[y-(1<<l)+1][l]);
}
long long Distance(int x,int y)
{
return dpt[x]+dpt[y]-2*LCA_Depth(x,y);
}
}
pair<long long,int> operator + (const pair<long long,int> x,const pair<long long,int> y)
{
return make_pair(x.first+y.first,x.second+y.second);
}
pair<long long,int> operator - (const pair<long long,int> x,const pair<long long,int> y)
{
return make_pair(x.first-y.first,x.second-y.second);
}
/*
struct Segtree{
Segtree *ls,*rs;
long long sum1;
int sum2;
//sum1代表子树中所有点到该点的距离之和
//sum2代表子树中点的个数
void* operator new(size_t)
{
static Segtree *mempool,*C;
if(C==mempool)
mempool=(C=new Segtree[1<<15])+(1<<15);
C->ls=C->rs=0x0;
C->sum1=C->sum2=0;
return C++;
}
friend void Insert(Segtree *&p,int x,int y,int pos,int val)
{
int mid=x+y>>1;
if(!p) p=new Segtree;
p->sum1+=val;
p->sum2++;
if(x==y) return ;
if(pos<=mid)
Insert(p->ls,x,mid,pos,val);
else
Insert(p->rs,mid+1,y,pos,val);
}
pair<long long,int> Query(Segtree *p,int x,int y,int l,int r)
{
int mid=x+y>>1;
if(!p) return make_pair(0ll,0);
if(x==l&&y==r)
return make_pair(p->sum1,p->sum2);
if(r<=mid)
return Query(p->ls,x,mid,l,r);
if(l>mid)
return Query(p->rs,mid+1,y,l,r);
return Query(p->ls,x,mid,l,mid) + Query(p->rs,mid+1,y,mid+1,r);
}
};
*/
namespace Dynamic_TDC{
using namespace Tree;
abcd sum1[M],sum2[M];
int fa[M];
int Get_Size(int x,int from)
{
int i,re=1;
for(i=head[x];i;i=table[i].next)
if(!table[i].ban&&table[i].to!=from)
re+=Get_Size(table[i].to,x);
return re;
}
int Get_Centre_Of_Gravity(int x,int from,int size,int &cg)
{
int i,re=1,flag=true;
for(i=head[x];i;i=table[i].next)
if(!table[i].ban&&table[i].to!=from)
{
int temp=Get_Centre_Of_Gravity(table[i].to,x,size,cg);
if(temp<<1>size)
flag=false;
re+=temp;
}
if(size-re<<1>size)
flag=false;
if(flag) cg=x;
return re;
}
void DFS(int x,int from,int dpt,abcd &sum1,abcd &sum2)
{
int i;
sum1.push_back(pair<int,long long>(a[x],dpt));
sum2.push_back(pair<int,long long>(a[x],dpt));
for(i=head[x];i;i=table[i].next)
if(!table[i].ban&&table[i].to!=from)
DFS(table[i].to,x,dpt+table[i].f,sum1,sum2);
}
int Tree_Divide_And_Conquer(int x)
{
abcd::iterator it;
int i,j,size=Get_Size(x,0);
Get_Centre_Of_Gravity(x,0,size,x);
sum1[x].push_back(pair<int,long long>(a[x],0));
for(i=head[x];i;i=table[i].next)
if(!table[i].ban)
{
table[i].ban=table[i^1].ban=true;
abcd temp;
DFS(table[i].to,0,table[i].f,temp,sum1[x]);
int y=Tree_Divide_And_Conquer(table[i].to);
sum2[y]=temp;fa[y]=x;
sum2[y].push_back(pair<int,long long>(-1,0));
sort(sum2[y].begin(),sum2[y].end());
for(j=1;j<sum2[y].size();j++)
sum2[y][j].second+=sum2[y][j-1].second;
}
sum1[x].push_back(pair<int,long long>(-1,0));
sort(sum1[x].begin(),sum1[x].end());
for(j=1;j<sum1[x].size();j++)
sum1[x][j].second+=sum1[x][j-1].second;
return x;
}
pair<long long,int> Query(abcd &a,int l,int r)
{
if(a.empty())
return pair<long long,int>(0,0);
abcd::iterator it1=lower_bound(a.begin(),a.end(),pair<int,long long>(l,0));
abcd::iterator it2=lower_bound(a.begin(),a.end(),pair<int,long long>(r+1,0));
it1--;it2--;
return make_pair(it2->second-it1->second,it2-it1);
}
long long Query(int x,int l,int r)
{
int i;
long long re=Query(sum1[x],l,r).first;
for(i=x;fa[i];i=fa[i])
{
pair<long long,int> temp=Query(sum1[fa[i]],l,r)-Query(sum2[i],l,r);
re+=temp.first+temp.second*Distance(x,fa[i]);
}
return re;
}
}
int main()
{
using namespace Tree;
using namespace Dynamic_TDC;
int i,x,y,z;
cin>>n>>m>>A;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
Add(x,y,z);Add(y,x,z);
}
DFS(1,0);Build_LCA();
Tree_Divide_And_Conquer(1);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
y=(y+last_ans)%A;
z=(z+last_ans)%A;
if(y>z) swap(y,z);
printf("%lld
",last_ans=Query(x,y,z));
}
return 0;
}
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
