admin 管理员组

文章数量: 887007

【队内胡策】ま ほう しょう じょ （马猴烧酒）DQS（树链剖分倍增LCA）

马猴烧酒 DQS
题目描述
魔法水晶承载着魔法师的法力，是魔法师法力的结晶。
魔法少女 DQS 拥有 n 个魔法水晶。为了让这 n 个魔法水晶处于相互联系的状态中，并且
不出现流动混乱，她用 n-1 条法力流动通道将魔法水晶联系起来。每条通道直接连接两个
魔法水晶，并且每对魔法水晶都直接或间接相连。
每条法力流动通道有一个延迟量，一对魔法水晶之间的延迟量是连接它们的路径上所有通道
的延迟量之和。n 个魔法水晶这一整体的总延迟是每对魔法水晶之间的延迟量的和。
并且 DQS 还会进行 m 次施法操作，每次施法会将连接魔法水晶 u 和 v 的路径上所
有的法力流动通道的延迟量增加 w。
她需要你帮助她动态地计算 n 个魔法水晶这一整体的总延迟。
输入描述
第一行一个数 n，接下来 n-1 行，每行三个数 a、b、c，表示有一条连接
a、b 的延迟量为 c 的法力流动通道。
接下来一个数 m，表示施法次数。接下来 m 行，每行三个数 u、v、w，表示
连接 u 和 v 的路径上的每一条法力流动通道的延迟量都增加 w。
输出描述
输出 m+1 行，第 i 行输出一个整数表示完成前(i-1)次施法操作后的总延
迟。
答案对 1,000,000,007 取模。
样例输入
3
1 2 2
1 3 1
2
1 2 -2
2 3 1
样例输出
6
2
6
数据范围及提示
20%的数据，n,m≤50
40%的数据，n,m≤300
60%的数据，n,m≤3000
另 20%的数据，m=0
100%的数据，n,m≤100000，-10^9≤c,w≤10^9
关于样例：
图中的树是一条链，其中(1,2)的延迟量为 2，(1,3)的延迟量为 1
定义 dis[i][j]为从 i，这一对魔法水晶的延迟量
第一次的总延迟量计算为 dis[1][2] + dis[1][3] + dis[2][3] = 2 + 1 + 3 = 6
在修改后，(1,2)的延迟量变成 0，(1,3)的延迟量变成 1
这时总延迟量计算为 dis[1][2] + dis[1][3] + dis[2][3] = 0 + 1 + 1 = 2
再次修改后，(1,2)的延迟量变成 1，(1,3)的延迟量变成 2
此时总延迟量计算为 dis[1][2] + dis[1][3] + dis[2][3] = 1 + 2 + 3 = 6

2333这个题是去年小兔子学长找姜大爷要的题。

考场上看到这个题，因为是T3，就没怎么敢做，打了个n^2貌似60分的暴力就交了，结果发现自己少算了一个n…所以 20分滚粗。

今天看到这个题….为什么我感觉能做。

看数据范围…100%的数据n<=十万。

两两之间的距离要怎么处理，直接暴力么?

暴力的话，点两两枚举…再加上暴力LCA，n^3啊….光是300就吃不消了，更别说十万了。

其实这个题我们可以不用模拟的…

你需要开脑洞。


这是一棵树，我们现在只看这树上的某一条边edge。

假设这条边连接的两个点，深度大的为v,深度小的为u。

那么那些点对会经过边edge呢？

很明显，是v的子树和v的上面的部分两两组成的点对会经过边edge。
那么边edge被经过了多少次呢？

是[siz[v] (以v为节点的子树大小)*n-(siz[v])]次。

试想一下，一条边把一棵树分成了两部分，一部分有x个点，另一部分有y个点，我们让他们两两配对，先从x集合中的一号点开始，则有…x1y1，x1y2…..x1yy，x2y1，x2y2….x2yy………..xxyy。
总的方案数是不是x*y？

所以说我想说什么呢？

我们处理的时候，处理出：每条边被记录了多少次就好了

先一个DFS处理出深度和子树大小，然后在O（n）的时间内就能求出每条边被记录的次数和初始的总延迟。

之后对于每个询问的a,b,c，我们直接用树剖维护a到b路径的区间和tot，tot就是你修改这一段区间会对多少条边造成影响，然后用每一次处理出来的延迟+（tot*c）就好啦。

不要忘了mod！
负数是不能mod的！
（之后还会有LCA的讲解和代码）


#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=200000+500;
const ll ha=1000000007;
ll n;
struct Edge
{ll f;ll to;ll d;ll next;
}edge[maxn];
ll head[maxn];
ll tot;
void add(ll f,ll t,ll d)
{edge[++tot].to=t;edge[tot].d=d%ha;edge[tot].next=head[f];head[f]=tot;
}
ll deep[maxn],fa[maxn],son[maxn];
ll siz[maxn];
void dfs1(ll f,ll t)
{fa[t]=f;deep[t]=deep[f]+1;siz[t]=1;for(ll i=head[t];i;i=edge[i].next){Edge e=edge[i];if(e.to==f)continue;dfs1(t,e.to);siz[t]+=siz[e.to];if(siz[e.to]>siz[son[t]])son[t]=e.to;}   
}
ll top[maxn],xds[maxn],xdscnt;
void dfs2(ll u,ll topu)
{top[u]=topu;xds[u]=++xdscnt;if(!son[u])return;dfs2(son[u],topu);for(ll i=head[u];i;i=edge[i].next){Edge e=edge[i];if(e.to==fa[u]||e.to==son[u])continue;dfs2(e.to,e.to);}
}
struct Tree
{ll l,r;ll sum;
}t[maxn<<2];
void up(ll p)
{t[p].sum=(t[p<<1].sum+t[p<<1|1].sum);   
}
void expand(ll p,ll l,ll r)
{t[p].l=l;t[p].r=r;if(l==r){return;}ll mid=(l+r)>>1;expand(p<<1,l,mid);expand(p<<1|1,mid+1,r);up(p);
}
void change(ll p,ll pos,ll v)
{if(t[p].l==t[p].r){t[p].sum=v%ha;return;}ll mid=(t[p].l+t[p].r)>>1;if(pos<=mid)change(p<<1,pos,v);elsechange(p<<1|1,pos,v);up(p);
}
ll cnt[maxn];
void clr()
{for(ll i=2;i<=n;i++)cnt[xds[i]]+=(siz[i]*(n-siz[i]));
}
ll ff[maxn],tt[maxn];
ll dd[maxn];
ll ask_sum(ll p,ll l,ll r)
{if(l<=t[p].l&&t[p].r<=r){return t[p].sum;}ll ans=0; ll mid=(t[p].l+t[p].r)>>1;if(l<=mid){ans+=ask_sum(p<<1,l,r);}if(mid+1<=r){   ans+=ask_sum(p<<1|1,l,r);}return ans;
}   
ll find_sum(ll x,ll y)
{ll fax=top[x],fay=top[y];ll tott=0;  while(fax!=fay){if(deep[fax]<deep[fay])swap(fax,fay),swap(x,y);tott+=ask_sum(1,xds[fax],xds[x]);x=fa[fax];fax=top[x];}if(deep[x]>deep[y])swap(x,y);if(x!=y)tott+=ask_sum(1,xds[x]+1,xds[y]);return tott%ha;
}
void read(ll &a)
{char c=getchar();ll flag=1;while(c<'0'||c>'9'){if(c=='-');flag=-1;c=getchar();}ll ans=0;while(c<='9'&&c>='0'){ans*=10;ans+=c-'0';c=getchar();}a=ans*flag;return;
}
int main()
{freopen("MaHouShaoJiuDQS.in","r",stdin);freopen("MaHouShaoJiuDQS.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<n;i++){scanf("%lld%lld%lld",&ff[i],&tt[i],&dd[i]);while(dd[i]<0)dd[i]+=ha;dd[i]%=ha;add(ff[i],tt[i],dd[i]);add(tt[i],ff[i],dd[i]);}dfs1(100500,1);dfs2(1,1);expand(1,1,n);clr();for(ll i=1;i<n;i++){if(deep[ff[i]]>deep[tt[i]])swap(ff[i],tt[i]);change(1,xds[tt[i]],cnt[xds[tt[i]]]);}ll anss=0;for(ll i=1;i<n;i++){anss+=(cnt[xds[tt[i]]]*dd[i])%ha;anss%=ha;}printf("%lld\n",anss%ha);ll m;scanf("%lld",&m);while(m--){ll a,b;ll c;scanf("%lld%lld%lld",&a,&b,&c);while(c<0)c+=ha;c%=ha;ll tot=find_sum(a,b)%ha;anss+=(tot*c);anss%=ha;printf("%lld\n",anss);}fclose(stdin);fclose(stdout); return 0;
}

LCA的话，我们在第一次DFS处理之后，在来一遍DFS，处理出根节点到所有点的（边的使用次数）距离。

然后用倍增LCA求出a到b的LCA，当前延迟直接加上（dist[a]+dist[b]-2*dist[LCA(a,b)]） * c就好啦。
（代码一会放….）
然而我在处理的时候搞着搞着就炸了….
一开始把图搞乱了…
其实有些地方还是和树剖的思想一样…我们把每条边的使用次数下放到深度较大的节点上…这个用一个DFS处理就可以。
定义数组cnt[i]表示从根节点到i节点这条路径上每条边使用了多少次的总和。

为什么我觉得一个普通的倍增LCA不如树剖好写…..

#include<cstring>
#include<cstdio>
#include<string>
#define maxn 200000+500
#define ha 1000000007 
using namespace std;
typedef long long ll;
struct Edge
{ll to;ll d;ll next;
}edge[maxn<<1];
ll n;
ll tot;
ll head[maxn];
void add(ll f,ll t,ll d)
{edge[++tot]=(Edge){t,d,head[f]};head[f]=tot;
}
ll deep[maxn],siz[maxn],fa[maxn][30];
void dfs1(int f,int t,int dep)
{deep[t]=dep;fa[t][0]=f;siz[t]=1;for(int i=head[t];i;i=edge[i].next){Edge e=edge[i];if(e.to!=f){dfs1(t,e.to,dep+1);siz[t]+=siz[e.to];}}
}
void clr()
{for(ll j=1;j<=25;j++)for(ll i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
}//预处理
ll cnt[maxn];
ll getcnt(ll x,ll y)
{if(deep[x]<deep[y])swap(x,y);return (siz[x]*(n-siz[x]))%ha;
}//上面推出来的式子
void dfs2(int x)
{cnt[x]=cnt[fa[x][0]]+getcnt(fa[x][0],x);//用奇♂怪的方式处理cntcnt[x]%=ha;for(int i=head[x];i;i=edge[i].next){Edge e=edge[i];if(e.to!=fa[x][0])dfs2(e.to);}
}
ll anss;
ll ff[maxn],tt[maxn],dd[maxn];
ll lca(ll x,ll y)
{if(deep[x]<deep[y])swap(x,y);for(int j=25;j>=0;j--)if(deep[fa[x][j]]>=deep[y])x=fa[x][j];if(x==y)return x;for(int j=25;j>=0;j--)if(fa[x][j]!=fa[y][j])x=fa[x][j],y=fa[y][j];return fa[x][0];            
}
void getans()
{for(int i=1;i<n;i++){ll tmp=getcnt(ff[i],tt[i])%ha;anss+=tmp*dd[i]%ha;anss%=ha;}
}//预处理最初的总延迟
int main()
{freopen("MaHouShaoJiuDQS.in","r",stdin);freopen("MaHouShaoJiuDQS.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<n;i++){scanf("%lld%lld%lld",&ff[i],&tt[i],&dd[i]);while(dd[i]<0)dd[i]+=ha;dd[i]%=ha;add(ff[i],tt[i],dd[i]);add(tt[i],ff[i],dd[i]);}dfs1(0,1,1);clr();dfs2(1);getans();ll m;printf("%lld\n",anss%ha);scanf("%lld",&m);while(m--){ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);c+=ha;c%+ha;ll tmp=(cnt[a]%ha+cnt[b]%ha-2*cnt[lca(a,b)]%ha)%ha;anss+=(tmp%ha*c%ha)%ha;while(anss<0)anss+=ha;printf("%lld\n",anss%ha);}return 0;
}

本文标签： 队内胡策ま ほう しょう じょ （马猴烧酒）DQS（树链剖分倍增LCA）

版权声明：本文标题：【队内胡策】ま ほう しょう じょ （马猴烧酒）DQS（树链剖分倍增LCA） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732356667h1534627.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。