cojR8

发表于 更新于 分类于 评论数： 阅读次数：

Source

好题：E、F

commetoj R8

E

请先思考后再展开

几乎是抄了一遍题解系列……
$$
\begin{aligned}
ans&=\sum_{i=1}^n ( \prod p_t^{\lfloor k_t/2 \rfloor} )=\sum_{i=1}^n ( i/\prod p_t^{\lceil k_t/2 \rceil} ) \\
&=\sum_{i=1}^n \sum_{j=1}^i[i|j^2]=\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^{j^2} [ik=j^2] \\
&看到乘积为完全平方数，考虑最大公约数\\
&=\sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{k=1}^i [gcd(i,k)=1] [i,k为完全平方数] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \sum_{k=1}^i [gcd(i^2,k^2)=1] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \varphi(i^2)=\sum_{i=1}^n \varphi(i) \lfloor n/i^2 \rfloor
\end{aligned}
$$

F 黄金体验

请先思考后再展开

有个不会证明但找不到反例的结论：k可以由k-1增量得到
那么如果静态的话，不难想到可以先求出k=2即带权直径，搞出一个端点作为根，然后k-1次找当前贡献最大的链并加入
仔细思考发现这东西本质上就是带权长剖，这种链的信息可以用lct来维护：
按照到根权值和从小到大access每个节点，得出带权长链，前k-1大长链之和就是答案

现在考虑怎么动态维护，更改一个节点，那么唯一的改动就是向上的长链
可以类似access那样，直到无法从轻儿子变为重儿子，这个过程中会有一系列长链的权值改动，要用segt维护
还有一个问题就是修改以后带权直径会变，但考虑到新的根可以从新带权直径任意一个端点中选择
而新直径一定会保留原本直径中的某个端点，以那个为根的话长链的结构是没有变化的，这方面在access的时候特判就好了

时间复杂度为 $O(qlog^2n)$
代码好写归好写，花了一上午，一个错误调一年

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
	#define double long double
	typedef long long ll;
	#define pr pair<int,int>
	#define FR first
	#define SE second
	#define MP make_pair
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) putchar('-'),num=-num;
		if(num>=10) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	const int INF=0x3f3f3f3f;
	int MOD=998244353;
	void add(ll &a,ll b){a+=b;a=(a>=MOD?a-MOD:(a<=-MOD?a+MOD:a));}
	ll qpower(ll x,ll e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int N=2e5+10;
	namespace PP
	{
		priority_queue<ll> a,b;
		ll top()
		{
			while(a.size() and b.size() and a.top()==b.top()) a.pop(),b.pop();
			return a.top();
		}
		void insert(ll num){a.push(num);}
		void del(ll num){b.push(num);}
	};
	namespace SGT
	{
		#define MID (l+r)/2
		struct Nod{int lc,rc,siz;ll sum;}p[N*80];
		int id=0,rt;
		void add(int &x,ll l,ll r,ll pos,int c)
		{
			if(!x) x=++id;
			p[x].siz+=c;p[x].sum+=pos*c;
			if(p[x].siz<0)
				puts("error");
			if(l==r) return;
			if(pos<=MID) add(p[x].lc,l,MID,pos,c);
			else add(p[x].rc,MID+1,r,pos,c);
		}
		ll ask(int x,ll l,ll r,int k)
		{
			if(!x) return 0;
			if(l==r) return l*min(k,p[x].siz);//debug
			int rr=p[p[x].rc].siz;
			if(k<=rr) return ask(p[x].rc,MID+1,r,k);
			return ask(p[x].lc,l,MID,k-rr)+p[p[x].rc].sum;
		}
		void change(ll pos,int c){add(rt,0,1e15,pos,c);}
	};
	ll w[N];
	namespace LCT
	{
		int fa[N],son[N][2];ll sum[N];
		int lc(int x){return son[x][0];}int rc(int x){return son[x][1];}
		bool tag[N];void rev(int x){tag[lc(x)]^=1;tag[rc(x)]^=1;swap(son[x][0],son[x][1]);tag[x]=0;}
		void pushup(int x){sum[x]=w[x]+sum[lc(x)]+sum[rc(x)];}
		bool sn(int x){return rc(fa[x])==x;}
		bool isrt(int x){return son[fa[x]][sn(x)]!=x;}
		void rotate(int x)
		{
			int f=fa[x],ff=fa[f];if(!isrt(f))son[ff][sn(f)]=x;
			int w=sn(x),gson=son[x][w^1];son[f][w]=gson;son[x][w^1]=f;
			fa[x]=ff;fa[f]=x;if(gson)fa[gson]=f;pushup(f);pushup(x);
		}
		vc<int> tmp;
		void splay(int x)
		{
			tmp.clear();int now=x;tmp.PB(now);while(!isrt(now)) tmp.PB(now=fa[now]);
			for(int t=(int)tmp.size()-1;t>=0;t--) if(tag[tmp[t]]) rev(tmp[t]);
			for(int f=fa[x];!isrt(x);rotate(x),f=fa[x]) if(!isrt(f)) sn(x)^sn(f)?rotate(x):rotate(f);
		}
		void add(int x,int val)
		{
			splay(x);SGT::change(sum[x],-1);w[x]+=val;sum[x]+=val;
			ll now=sum[x];//debug
			int lst=x,nxt=fa[x];
			while(nxt)
			{
				splay(nxt);
				if(fa[nxt]==0 and sum[lc(nxt)]<sum[rc(nxt)] and now>sum[lc(nxt)])//rt
				{
					SGT::change(sum[nxt],-1);SGT::change(sum[lc(nxt)],1);
					int oth=nxt;while(1){if(tag[oth])rev(oth);if(!rc(oth))break;oth=rc(oth);}//debug
					splay(oth);tag[oth]^=1;splay(nxt);son[nxt][1]=lst;break;
				}
				ll old=sum[rc(nxt)];if(now<=old) break;
				SGT::change(sum[nxt],-1);SGT::change(old,1);
				now+=w[nxt]+sum[lc(nxt)];son[nxt][1]=lst;
				lst=nxt;nxt=fa[nxt];
			}
			splay(x);SGT::change(sum[x],1);
		}
	};
	vc<int> to[N];
	void pre(int x,int fa)
	{
		LCT::fa[x]=fa;
		for(int t=0;t<(int)to[x].size();t++) if(to[x][t]!=fa) pre(to[x][t],x);
	}
	void main()
	{
		int n=qread();
		for(int i=1;i<n;i++){int x=qread(),y=qread();to[x].PB(y);to[y].PB(x);}
		SGT::change(0,n);pre(1,0);for(int i=1;i<=n;i++) LCT::add(i,qread()),PP::insert(w[i]);
		int q=qread();
		while(q--)
		{
			int op=qread();
			if(op==0){int x=qread();PP::del(w[x]);LCT::add(x,qread());PP::insert(w[x]);}
			else
			{
				int k=qread();
				if(k==1) write2(PP::top());
				else write2(SGT::ask(SGT::rt,0,1e15,k-1));
			}
		}
	}//x+MOD
};
int main()
{
	freopen("a.in","r",stdin);
	srand(time(0));
	mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/b2c5.html
转载请注明出处，谢谢！