首页 > 代码库 > 特教的理性愉悦
特教的理性愉悦
一个不知名的神犇发的一套NOIp模拟题的T3。
其他的很好搞定,问题是如何求一段路径上任意两点之间的路径和。
首先很容易想到的是把最暴力枚举两点的距离变成枚举边然后利用乘法原理计算每条边对答案的贡献,一次计算复杂度为$O(N)$。显然要在这之上进行优化。
如何把每次的枚举变成前缀和的计算?这是要思考的问题,但是单纯的前缀和显然不可行。因为每条边的前系数会根据每条边左边和右边有多少个点而变化。根据这一点可以通过在前缀和中引入深度。通过一些处理就可以搞定第一个系数。但是每个系数前还有一个系数。所以再在求前缀和中引入深度的平方,然后再经过一些神奇的处理就能得到答案啦!
//ecstasy//by Cydiater//2016.10.24#include <iostream>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <ctime>#include <cmath>#include <iomanip>#include <cstring>#include <string>#include <algorithm>#include <bitset>using namespace std;#define ll long long#define up(i,j,n) for(int i=j;i<=n;i++)#define down(i,j,n) for(int i=j;i>=n;i--)#define FILE "ecstasy"const ll MAXN=1e5+5;const ll oo=1LL<<60;inline ll read(){ char ch=getchar();ll x=0,f=1; while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}ll N,M,fa[MAXN][30],f[MAXN],dep[MAXN],dis[MAXN],ndis[MAXN],n2dis[MAXN],LINK[MAXN],len=0;struct edge{ ll y,next,v;}e[MAXN<<1];struct Ask{ ll opt,x,y,v,ans;}ask[MAXN<<3];namespace solution{ inline void insert(ll x,ll y,ll v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} int getf(int k){ if(f[k]==k) return k; f[k]=getf(f[k]); return f[k]; } void dfs(int node,int deep,int father){ fa[node][0]=father;dep[node]=deep; for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=father){ dis[e[i].y]=dis[node]+e[i].v; ndis[e[i].y]=ndis[node]+(N-dep[node])*e[i].v; n2dis[e[i].y]=n2dis[node]+(N-dep[node])*(N-dep[node])*e[i].v; dfs(e[i].y,deep+1,node); } } void get_ancstor(){ up(i,1,20)up(node,1,N)if(fa[node][i-1]!=0) fa[node][i]=fa[fa[node][i-1]][i-1]; } void init(){ N=read();M=read(); up(i,1,N)f[i]=i; up(i,1,M){ ll opt=read(),x=read(),y=read(),v; if(opt==1){ v=read(); f[getf(x)]=getf(y); insert(x,y,v); insert(y,x,v); }else if(getf(x)!=getf(y))ask[i].ans=-1; ask[i].opt=opt;ask[i].x=x;ask[i].y=y;ask[i].v=v; } dfs(1,0,0); get_ancstor(); } int LCA(int x,int y){ if(x==y) return x; if(dep[x]<dep[y])swap(x,y); down(i,20,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i]; if(x==y) return x; down(i,20,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } ll get(ll x,ll y){ int lca=LCA(x,y);ll num=dep[x]+dep[y]-(dep[lca]<<1); ll ixsum=ndis[x]-ndis[lca]-(dis[x]-dis[lca])*(N-dep[x]); ll iysum=ndis[y]-ndis[lca]-(dis[y]-dis[lca])*(N-dep[y]); ll i2xsum=n2dis[x]-n2dis[lca]-(dis[x]-dis[lca])*(N-dep[x])*(N-dep[x])-(N-dep[x])*(ixsum<<1); ll i2ysum=n2dis[y]-n2dis[lca]-(dis[y]-dis[lca])*(N-dep[y])*(N-dep[y])-(N-dep[y])*(iysum<<1); return (num+1)*(ixsum+iysum)-i2xsum-i2ysum; } void slove(){ up(i,1,M)if(ask[i].opt==2&&ask[i].ans!=-1) ask[i].ans=get(ask[i].x,ask[i].y); } void output(){ up(i,1,M)if(ask[i].opt==2) printf("%I64d\n",ask[i].ans); }}int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); using namespace solution; init(); slove(); output(); return 0;}
特教的理性愉悦
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。