闲着无聊打了一下
发现我非常的愚蠢
a签到
b我写了个数位dp
其实上界松了的时候答案直接是一半，这样可以写起来更简单
c题大概是二分之后再O(n)搞一下
被k=0卡的怀疑人生，一度以为是爆ll
d题考虑整数分块+对数据分块
对于整数分块之后,我们要维护的是i-k,i-2k,i-3k,i-4k,对于k<=sqrt(n),我们用数组维护
对于k>sqrt(n)，我们暴力维护
e题
结论是a*b-k1a-k2b都是不可行的 (k1>0,k2>0)
比较常规的做法是用堆维护最小然后不断更新，但这样是带log的
可以维护两个指针代表-a,-b然后从大到小扫过去
另外一种做法是
二分一下值，然后枚举大的算小的
易知一次是根号，复杂度sqrt(n)log(n)
f题
赛后和队友讨论了一下可以虚树
大概是建出虚树之后对每块操作可以看成是两个子树的差
然后对其的贡献可以用两次dfs实现
nlogn 然后1e6读入输出 1s题就离谱
正解是O(n)的
比较难想，是看着别人代码学的。。
考虑答案可以变成n*n-((i->j)上未出现的点)
考虑答案从x变到儿子y,可以知道对于子树来说到未出现a[x]这个值的路径都是要减掉的
这个比较妙可以利用两个的差去维护(我本来想得是启发式合并维护)
另外从y到外面这些点的路径 是要加上去的
这个也可以通过O(1)维护
大致是进y时，把g[a[x]]的值变成x到子树中有y的点的数量
因为对于y来说，a[y]现在新覆盖的范围就是祖先中第一个颜色是a[y]的往下一步的子树中的一个连通块
把g[a[y]]=0 因为进到当前点子树后到外面的路径肯定都经过了a[y]
说起来很难说，但反正挺妙的
代码照着标算写竟然tle了就离谱懒得卡常了
#include <bits/stdc++.h> using namespace std; #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long #define me(x) memset(x,0,sizeof(x)) #define IL inline #define rint register int inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T>void maxa(T &x,T y) { if (y>x) x=y; } template<class T>void mina(T &x,T y) { if (y<x) x=y; } template<class T>void read(T &x) { int f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f; } const int mo=1e9+7; ll fsp(int x,int y) { if (y==1) return x; ll ans=fsp(x,y/2); ans=ans*ans%mo; if (y%2==1) ans=ans*x%mo; return ans; } struct cp { ll x,y; cp operator +(cp B) { return (cp){x+B.x,y+B.y}; } cp operator -(cp B) { return (cp){x-B.x,y-B.y}; } ll operator *(cp B) { return x*B.y-y*B.x; } int half() { return y < 0 || (y == 0 && x < 0); } }; struct re{ int a,b,c; }; const int N=2e6; ll n; ll a[N]; char sr[1<<26],z[50]; int C=-1,Z; template <class T> void wer(T x) { if (x<0) sr[++C]='-',x=-x; while (z[++Z]=x%10+48,x/=10); while (sr[++C]=z[Z],--Z); sr[++C]=' '; } vector<int> ve[N]; ll g[N],vis[N],size[N],g2[N],p[N],g3[N],g4[N]; ll ans[N],ans2[N]; void dfs(int x,int y) { size[x]=1; ll now=p[a[x]],now2=p[a[y]]; for (auto v:ve[x]) if (v!=y) { dfs(v,x); size[x]+=size[v]; } if (y) g2[x]=size[x]-(p[a[y]]-now2); p[a[x]]=now+size[x]; } void dfs2(int x,int y) { ans[x]=g2[x]+ans[y]-g3[a[x]]; ll p1=g3[a[y]],p2=g3[a[x]]; g3[a[y]]=g2[x]; g3[a[x]]=0; ans2[x]=1ll*n*n-ans[x]; for (auto v:ve[x]) if (v!=y) { dfs2(v,x); } g3[a[y]]=p1; g3[a[x]]=p2; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); read(n); rep(i,1,n) read(a[i]); rep(i,1,n-1) { int x,y; read(x); read(y); ve[x].push_back(y); ve[y].push_back(x); } dfs(1,0); rep(i,1,n) g3[i]=n-p[i],g2[1]+=g3[i]; dfs2(1,0); rep(i,1,n) wer(ans2[i]); fwrite(sr,1,C+1,stdout); return 0; }