[SimpleOJ238]宝藏探寻

题目大意：
　　给你一棵带点权的n个结点的树，有m次询问，每次从树上删掉一条路径(u,v)，问删掉每条路径后各个连通块权值和的平方之和。
　　每次询问是独立的。

思路：
　　首先对树遍历一遍求出每棵子树的权值和。
　　然后倍增记录下每个结点往上跳2^k层，深度范围内与这条路径无关的每个连通块的权值和的平方之和。
　　然后询问的时候直接倍增往上跳即可，注意跳最后一层的时候要特判一下。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 typedef long long int64;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 int w[N],sum[N],par[N],dep[N];

 std::vector<int> e[N];

 inline void add_edge(const int &u,const int &v) {

     e[u].push_back(v);

     e[v].push_back(u);

 }

 void dfs(const int &x,const int &p) {

     par[x]=p;

     dep[x]=dep[p]+;

     sum[x]=w[x];

     for(register unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==p) continue;

         dfs(y,x);

         sum[x]+=sum[y];

     }

 }

 inline int64 sqr(const int64 &x) {

     return x*x;

 }

 inline int lca(int x,int y) {

     while(x!=y) {

         if(dep[x]<dep[y]) std::swap(x,y);

         x=par[x];

     }

     return x;

 }

 inline int64 solve(int x,int y) {

     int64 ans=;

     if(x==y) {

         for(register unsigned i=;i<e[x].size();i++) {

             const int &y=e[x][i];

             if(y==par[x]) continue;

             ans+=sqr(sum[y]);

         }

         ans+=sqr(sum[]-sum[x]);

         return ans;

     }

     if(x!=lca(x,y)) {

         for(register unsigned i=;i<e[x].size();i++) {

             const int &y=e[x][i];

             if(y==par[x]) continue;

             ans+=sqr(sum[y]);

         }

     }

     std::swap(x,y);

     if(x!=lca(x,y)) {

         for(register unsigned i=;i<e[x].size();i++) {

             const int &y=e[x][i];

             if(y==par[x]) continue;

             ans+=sqr(sum[y]);

         }

     }

     while(par[x]!=par[y]&&x!=y) {

         if(dep[x]<dep[y]) std::swap(x,y);

         for(register unsigned i=;i<e[par[x]].size();i++) {

             const int &y=e[par[x]][i];

             if(y==par[par[x]]||y==x) continue;

             ans+=sqr(sum[y]);

         }

         x=par[x];

     }

     if(x!=y) {

         for(register unsigned i=;i<e[par[x]].size();i++) {

             const int &to=e[par[x]][i];

             if(to==par[par[x]]||to==x||to==y) continue;

             ans+=sqr(sum[to]);

         }

         x=par[x];

     }

     ans+=sqr(sum[]-sum[x]);

     return ans;

 }

 int top;

 void dfs1(const int &x,const int &par) {

     top=x;

     for(register unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         dfs1(y,x);

     }

 }

 int sum2[N];

 void dfs2(const int &x,const int &par) {

     sum2[x]=sum[par]+w[par];

     dep[x]=dep[par]+;

     for(register unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i];

         if(y==par) continue;

         dfs2(y,x);

         sum[x]=sum[y]+w[y];

     }

 }

 int main() {

     int n=getint(),m=getint();

     for(register int i=;i<=n;i++) {

         w[i]=getint();

     }

     for(register int i=;i<n;i++) {

         add_edge(getint(),getint());

     }

     if(n%==) {

         dfs1(,);

         dfs2(top,);

         while(m--) {

             int x=getint(),y=getint();

             if(dep[x]<dep[y]) std::swap(x,y);

             printf("%lld\n",sqr(sum[x])+sqr(sum2[y]));

         }

         return ;

     }

     dfs(,);

     while(m--) {

         printf("%lld\n",solve(getint(),getint()));

     }

     return ;

 }

巴特西

[SimpleOJ238]宝藏探寻

最新文章

热门文章