利用树剖序的一些性质~
这个题可以出到 $sum k=10^5$ 左右.
做法很简单：每次暴力跳重链，并在线段树上查询链和.
查询之后打一个标记，把加过的链都置为 $0$.
这样的话在同一次询问时即使有重复的也无所谓.
然后本次查询后在线段树的 $1$ 号节点再打一个标记，用来将那些置零的标记清空.
这个主要是利用树剖序的连续性质.
具体细节还是需要注意一下.
Code:
#include <cstdio>
#include <algorithm>
#define N 200004
#define ll long long
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
const ll mod=2147483648;
void Add(ll &g,ll b)
{
g=(g+b)%mod;
}
namespace seg
{
struct Node
{
int tag,mark;
ll sum,sumvir,add;
}t[N<<2];
void mark_tag(int now)
{
t[now].mark=1,t[now].tag=0,t[now].sum=t[now].sumvir;
}
void mark_add(int l,int r,int now,ll v)
{
Add(t[now].add,v), Add(t[now].sumvir,(r-l+1)*v%mod);
if(t[now].tag) t[now].sum=0;
else t[now].sum=t[now].sumvir;
}
void pushdown(int l,int r,int now)
{
int mid=(l+r)>>1;
if(t[now].mark)
{
if(mid>=l) mark_tag(now<<1);
if(r>mid) mark_tag(now<<1|1);
t[now].mark=0;
}
if(t[now].add)
{
if(mid>=l) mark_add(l,mid,now<<1,t[now].add);
if(r>mid) mark_add(mid+1,r,now<<1|1,t[now].add);
t[now].add=0;
}
}
void pushup(int l,int r,int now)
{
int mid=(l+r)>>1;
t[now].sum=t[now].sumvir=0;
if(mid>=l) Add(t[now].sum,t[now<<1].sum),Add(t[now].sumvir,t[now<<1].sumvir);
if(r>mid) Add(t[now].sum,t[now<<1|1].sum),Add(t[now].sumvir,t[now<<1|1].sumvir);
if(t[now].tag) t[now].sum=0;
}
void update_tag(int l,int r,int now,int L,int R)
{
if(l>=L&&r<=R)
{
t[now].tag=1,t[now].sum=t[now].mark=0;
return;
}
pushdown(l,r,now);
int mid=(l+r)>>1;
if(L<=mid) update_tag(l,mid,now<<1,L,R);
if(R>mid) update_tag(mid+1,r,now<<1|1,L,R);
pushup(l,r,now);
}
void update_add(int l,int r,int now,int L,int R,ll v)
{
if(l>=L&&r<=R)
{
mark_add(l,r,now,v);
return;
}
pushdown(l,r,now);
int mid=(l+r)>>1;
if(L<=mid) update_add(l,mid,now<<1,L,R,v);
if(R>mid) update_add(mid+1,r,now<<1|1,L,R,v);
pushup(l,r,now);
}
ll query(int l,int r,int now,int L,int R)
{
if((l>=L&&r<=R)||(t[now].tag)) return t[now].sum;
int mid=(l+r)>>1;
pushdown(l,r,now);
ll re=0;
if(L<=mid) Add(re,query(l,mid,now<<1,L,R));
if(R>mid) Add(re,query(mid+1,r,now<<1|1,L,R));
return re;
}
};
int n,Q,edges,tim;
int hd[N],to[N<<1],nex[N<<1],val[N];
int size[N],son[N],top[N],dfn[N],fa[N],dep[N],st[N],ed[N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs1(int u,int ff)
{
fa[u]=ff,dep[u]=dep[ff]+1,size[u]=1;
for(int i=hd[u];i;i=nex[i])
if(to[i]!=ff)
{
dfs1(to[i],u),size[u]+=size[to[i]];
if(size[to[i]]>size[son[u]]) son[u]=to[i];
}
}
void dfs2(int u,int tp)
{
top[u]=tp,st[u]=dfn[u]=++tim;
if(son[u]) dfs2(son[u],tp);
for(int i=hd[u];i;i=nex[i])
if(to[i]!=fa[u]&&to[i]!=son[u]) dfs2(to[i],to[i]);
ed[u]=tim;
}
ll work(int x,int y)
{
ll re=0;
while(top[x]!=top[y])
{
if(dep[top[y]]>dep[top[x]]) swap(x,y);
Add(re,seg::query(1,n,1,dfn[top[x]],dfn[x]));
seg::update_tag(1,n,1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
Add(re,seg::query(1,n,1,dfn[y],dfn[x]));
seg::update_tag(1,n,1,dfn[y],dfn[x]);
return re;
}
int main()
{
int i,j;
// setIO("input");
scanf("%d",&n);
for(i=1;i<n;++i)
{
int u,v;
scanf("%d%d",&u,&v),add(u,v),add(v,u);
}
dfs1(1,0),dfs2(1,1);
scanf("%d",&Q);
for(int cas=1;cas<=Q;++cas)
{
int opt;
scanf("%d",&opt);
if(opt==0)
{
int u;
ll v;
scanf("%d%lld",&u,&v);
seg::update_add(1,n,1,st[u],ed[u],v);
}
if(opt==1)
{
ll ans=0;
int k,u,v;
scanf("%d",&k);
for(i=1;i<=k;++i) scanf("%d%d",&u,&v), Add(ans,work(u,v));
seg::mark_tag(1);
printf("%lld
",ans);
}
}
return 0;
}