jsp网站怎么做邮箱验证码,东莞企业公司网站建设,西安公司注册核名,深圳网站设计 制作题目 这真是一道神仙的一批的题目 定义\(s(i,j)\)表示从点\(i\)到点\(j\)经过的颜色数量 设 \[sum_i\sum_{j1}^ns(i,j)\] 求出所有的\(sum_i\) 考虑点分治 对于一个点我们用两种方式来统计其答案 这个点作为分治重心时#xff0c;分值区域内所有点到这个点贡献这个点不是分治重… 题目 这真是一道神仙的一批的题目 定义\(s(i,j)\)表示从点\(i\)到点\(j\)经过的颜色数量 设 \[sum_i\sum_{j1}^ns(i,j)\] 求出所有的\(sum_i\) 考虑点分治 对于一个点我们用两种方式来统计其答案 这个点作为分治重心时分值区域内所有点到这个点贡献这个点不是分治重心的时候当前分治区域内其他子树到这个点的贡献第一种贡献我们很好统计点分治的时候把所有子树遍历一遍就好了 第二种就需要转换一下思路了我们不能直接求\(s(i,j)\)了我们应该求某一种颜色一共被数了多少次 我们开一个桶\(tax\)\(tax[i]\)表示\(i\)这种颜色控制的大小一共是多少也就是这个颜色会被多少个终点数到我们可以通过提前遍历好所有子树得到这个信息 每次进入一棵子树的时候提前减掉这个子树的贡献之后进入子树\(dfs\)就好了如果一旦出现一种新颜色显然这种颜色会被当前分治区域内所有点数上更改一下贡献即可 代码 #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includevector
#define maxn 100005
#define re register
#define inf 99999999
#define LL long long
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
inline int read() {int x0;char cgetchar();while(c0||c9) cgetchar();while(c0c9) x(x3)(x1)c-48,cgetchar();return x;
}
struct E{int v,nxt;}e[maxn1];
int col[maxn],head[maxn],vis[maxn],sum[maxn],mx[maxn];
int f[maxn],tax[maxn],d[maxn],st[maxn],tmp[maxn];
int num,n,m,now,S,rt,top;
LL ans,Ans[maxn],res;
std::vectorint v[maxn],c[maxn];
inline void add(int x,int y) {e[num].vy;e[num].nxthead[x];head[x]num;}
void getroot(int x,int fa) {sum[x]1,mx[x]0;for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]||e[i].vfa) continue;getroot(e[i].v,x);sum[x]sum[e[i].v],mx[x]max(mx[x],sum[e[i].v]);}mx[x]max(mx[x],S-sum[x]);if(mx[x]now) nowmx[x],rtx;
}
void getdis(int x,int fa,int now,int t) {if(!f[col[x]]) now;if(!tmp[col[x]]) st[top]col[x];tmp[col[x]]1;sum[x]1;f[col[x]];Ans[t]now;for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]||e[i].vfa) continue;getdis(e[i].v,x,now,t);sum[x]sum[e[i].v];}if(f[col[x]]1) d[col[x]]sum[x];f[col[x]]--;
}
void find(int x,int fa) {if(!f[col[x]]) ans-tax[col[x]],ansres;Ans[x]ans;f[col[x]];for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]||e[i].vfa) continue;find(e[i].v,x);} if(f[col[x]]1) ans-res,anstax[col[x]];f[col[x]]--;
}
void dfs(int x) {vis[x]1;ans0;f[col[x]]1;for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]) continue;top0;getdis(e[i].v,0,1,x);for(re int j1;jtop;j) if(st[j]!col[x]) v[e[i].v].push_back(d[st[j]]),c[e[i].v].push_back(st[j]);for(re int j1;jtop;j) if(st[j]!col[x]) tax[st[j]]d[st[j]],ansd[st[j]];for(re int j1;jtop;j) tmp[st[j]]0,d[st[j]]0;}f[col[x]]0;ansS,tax[col[x]]S;for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]) continue;resS-sum[e[i].v];ans-sum[e[i].v],tax[col[x]]-sum[e[i].v];for(re int j0;jv[e[i].v].size();j) ans-v[e[i].v][j],tax[c[e[i].v][j]]-v[e[i].v][j];find(e[i].v,0);for(re int j0;jv[e[i].v].size();j) ansv[e[i].v][j],tax[c[e[i].v][j]]v[e[i].v][j];anssum[e[i].v],tax[col[x]]sum[e[i].v];}for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]) continue;for(re int j0;jv[e[i].v].size();j)tax[c[e[i].v][j]]-v[e[i].v][j];v[e[i].v].clear(),c[e[i].v].clear();}tax[col[x]]0;for(re int ihead[x];i;ie[i].nxt) {if(vis[e[i].v]) continue;nowinf,Ssum[e[i].v],getroot(e[i].v,0),dfs(rt);}
}
int main() {nread();int x,y;for(re int i1;in;i) col[i]read();for(re int i1;in;i) xread(),yread(),add(x,y),add(y,x);Sn,nowinf,getroot(1,0);dfs(rt);for(re int i1;in;i) printf(%lld\n,Ans[i]1ll);return 0;
} 转载于:https://www.cnblogs.com/asuldb/p/10425326.html
