kczno1的博客官方,网上题解似乎都是$O(nlogn)$的
$dp[i]$表示$1..i$的$min$
则$dp[i]=min(dp[j-1]+max(h[j..i]))$ 且$w(j)+..w(i)<=L$
从左到右枚举$i$，
则所有$j$被所有$h[k]=max(h[k..i])$的$k$分成一段一段
每段由于$dp[j]$的单调递增肯定取最左边的那个$j$
$k$可以用单调栈维护
由于$w(j)+..w(i)$的限制，可以的$j$的左边界是单调左移的
我想了一个$O(n)$的方法，而且是能解决两端插入的 (求问有没有别的方法)
就是左右各开一个栈维护最值，
左边删除插入就用左边的
右边删除插入就用右边的
如果左或右的栈删没了，就重构，把队列分成两半，左边分一半，右边分一半
每次重构的时间复杂度和下次删完所需的时间是一样的，所以复杂度是线性的。
卡常后拿了bzoj rank1
网上题解似乎都是可并堆。
这题可以给每个点自己+1,上面第一个距离>=l的祖先-1，然后统计子树和，即为答案。
求那个祖先可以dfs一遍，把点存在栈里，然后二分。
$O(nlogn)$
能拿bzoj rank1。
#include<cstdio>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
template <typename T> inline void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
#define gc (*++now_r)
#define c *now_r
void read(int &x)
{
while(gc<'0');
x=c-'0';
while(gc>='0')x=x*10+c-'0';
}
void read(ll &x)
{
while(gc<'0');
x=c-'0';
while(gc>='0')x=x*10+c-'0';
}
#undef gc
#undef c
void write(int x)
{
static char st[20];
int top=0;
do{st[++top]='0'+x%10;}while(x/=10);
do{*++now_w=st[top];}while(--top);
*++now_w='\n';
}
const int N=2e5+5;
int n,t[N],nex[N];
ll l,a[N];
ll st[N];int stx[N],top;
int s[N];
void find(const ll &ns,int r)//将第一个<=ns的祖先-1
{
int l=1;
if(st[r]<=ns){--s[stx[r]];return ;}
#define mid (l+r>>1)
while(l+1!=r)
if(st[mid]<=ns)l=mid;
else r=mid;
--s[stx[l]];
}
void dfs(int x,const ll &ns,int dep)
{
st[dep]=ns;stx[dep]=x;
if(ns>=l)
{
find(ns-l,dep-1);
}
s[x]=1;
for(int y=t[x];y;y=nex[y])
{
dfs(y,ns+a[y],dep+1);
s[x]+=s[y];
}
}
int main()
{
freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
ch[fread(ch,1,ch_top,stdin)]=0;
read(n);read(l);l+=1;
rep(i,2,n)
{
int x;
read(x);read(a[i]);
nex[i]=t[x];t[x]=i;
}
dfs(1,0,1);
rep(i,1,n)write(s[i]);
fwrite(ch,1,now_w-ch+1,stdout);
}这题很多人都用DP+可并堆
也有很多人暴力上堆 复杂度是$klogk$乘上128以内的质因数个数，约30(不过实际效果挺好的)
然而直接上堆，可以做到$2*k$次$push$,$k$次$pop$ 。
首先枚举所有可能的最大质因子及质因子分解的项数
这样题目的限制就没了，每次拓展时就可以除掉一个质因数再乘上一个质因数(只要别把最大质因子除没了)
考虑如何可以使得所有数会被拓展到且只会被拓展到一次
一个想法就是每次拓展时除掉最小质因子再乘上其前驱(比它小的最大质数)
但对于一个有多个质因子的数这样还是不能拓展到
所以再加一个方向:除掉最大质因子再乘上最小质因子
这样就ok了。
$O(klogk)$
拿到了bzoj rank3。 (下面这个直接用priority_queue的就能拿rank5，后来我手写了二叉堆。 我还写了配对堆，但不知道为什么慢了一倍多)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=128;
int pr[N],cnt;
struct point
{
ll a;
int b,c,d;
point( ll a , int b , int c , int d ) : a( a ) , b( b ) , c( c ) , d( d ) {}
};
bool operator <(const point &p1,const point &p2)
{
return p1.a<p2.a;
}
priority_queue<point> h;
bool is_p(int x)
{
for(int i=2;i*i<=x;++i)
if(x%i!=0) return 0;
return 1;
}
int main()
{
//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
ll n;int k;
cin>>n>>k;
rep(i,2,N)
if(is_p(i))
{
pr[++cnt]=i;
ll a=1;
for(int j=1;a<=n/i;++j)
{
a*=i;
h.push( point(a,i,0,0) );
if(cnt>1&&j>1)
h.push( point(a/i*pr[cnt-1],i,j-1,cnt-1) );
}
}
while(--k)
{
point now=h.top();
h.pop();
if(now.d>1)
h.push( point( now.a/pr[now.d]*pr[now.d-1],now.b,now.c,now.d-1 ) );
if(now.c>1)
h.push( point( now.a/now.b*pr[now.d],now.b,now.c-1,now.d ) );
}
cout<<h.top().a;
}https://v.qzyz.com/problem/show/2711
没有题解我来发一个。
有环删安全值最小，相当于维护安全值的最大生成树;
安全值一样删最后，相当于以排列中的位置为第二关键字(升序)。
如果要求最大价值，就按安全值为第一关键字(降序)，价值为第二关键字(降序)排序做kruscal
但还要让排列的字典序最小
就贪心枚举每一位，从小到大枚举这一位填什么，然后判断是否可以达到最大价值。
判断的方法就是按安全值为第一关键字(降序)，排列中的位置为第二关键字(升序)，价值为第三关键字(降序)排序做kruscal
(对不在排列中的边就令他们位置都为最大)
(一开始我令在排列中的边位置都为最小。。居然还过了)
每次只改变一条边的位置，不用重新排序，可以直接特判
所以复杂度$O(m^3)$
(好像说有$mlogm$的做法？我不会)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rep0(i,n) for(int i=0;i<n;++i)
#define gc (c=getchar())
int read()
{
char c;
while(gc<'0');
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
const int N=300+5;
int n,m,fa[N];
struct edge
{
int x,y,p,c,dy;
}l[N];int nex[N],pre[N];
int dy[N];
bool operator <(const edge &e1,const edge &e2)
{
if(e1.p!=e2.p) return e1.p>e2.p;
return e1.c>e2.c;
}
int ans;
namespace get
{
int ans;
int find(int x)
{
return fa[x]==0?x:fa[x]=find(fa[x]);
}
void add(int i)
{
edge *it=l+i;
int x=find(it->x),y=find(it->y);
if(x==y)return ;
fa[x]=y;ans+=it->c;
}
int g(int x)
{
memset(fa+1,0,n*sizeof(int));
ans=0;
int i=1;
while(i<=m)
{
if(i==pre[x])add(x);
int j=nex[i];
rep(k,i,j-1)add(k);
i=j;
}
return ans;
}
};
int main()
{
freopen("1.in","r",stdin);
cin>>n>>m;
rep(i,1,m)l[i]=(edge){read(),read(),read(),read(),i};
sort(l+1,l+m+1);
rep(i,1,m)dy[l[i].dy]=i;
nex[m]=m+1;
for(int i=m;--i;)
if(l[i].p==l[i+1].p) nex[i]=nex[i+1];
else nex[i]=i+1;
nex[0]=1;
rep(i,1,m)
if(nex[i-1]==i)
rep(j,i,nex[i]-1)
pre[j]=i;
ans=get::g(0);
cout<<ans<<endl;
static bool in[N];
int top=0;
while(++top<=m)
{
int i=0;
while(++i<=m)
if(!in[i])
{
in[i]=1;
int x=dy[i];
if(get::g(x)==ans)
{
int j=pre[x];
while(x!=j)
{
swap(l[x],l[x-1]);swap(dy[l[x].dy],dy[l[x-1].dy]);
--x;
}
while(++j<nex[x]) pre[j]=x+1;
nex[x]=x+1;
break;
}
in[i]=0;
}
printf("%d ",i);
}
}stl的vector太慢了
还是手写的好
upd: 有一件很神奇的事情，就是我第一次pb的时候会分配0的空间，似乎是不对的，但我已经用了多次且没有出锅。。。
但还是多分配一个空间好了
#include<bits/stdc++.h>
using namespace std;
template<typename T>
struct vec
{
T *a;
int n;
void clear()
{
//if (n>0) {free(a);a=0;}
n=0;
}
void pb(const T &x)
{
if((n&-n)==n)//a=(T*)realloc(a,(n*2+1)*sizeof(T));
{
T *_a=new T [n*2+1];
memcpy(_a,a,n*sizeof(T));
a=_a;
}
a[n++]=x;
}
};
vec<int> a;
#define fore(arr) for(auto it=arr.a,end=it+arr.n;it!=end;++it)
int main()
{
a.pb(1);
fore(a) printf("%d\n",*it);
a.clear();
a.pb(2);
fore(a) printf("%d\n",*it);
}标算复杂度似乎是$O(3^{n}*n^2)$的，但可以$O(2^{n}*n^3)$
首先枚举哪些点是叶子。(设枚举的点集为 $s_1$,剩下的点集为 $s_2$)
如何保证一个点 $i$ 是叶子？
只要让 $i$ 往 $s_2$ 连一条边就可以了。
所以方案数 $f[s_1]=$ $s_2$ 的生成树个数 $ \times \prod_{i,i \in s_1}$ $i$ 连向 $s_2$ 的边数。前一项可以用矩阵树求
但这样其实只能保证 ${\textbf s_1}$ 的点是叶子，却不能保证 ${\textbf s_2}$ 的点不是叶子。
现在要求只有 ${\textbf s}$ 的点是叶子的方案数 $ans[s]$，就再容斥一下:
$ ans[s]=\sum_{s',s' \supseteq s } f[s'] * (-1)^{|s'|-|s|} $
这个东西如果暴力的话因为每个点有三种状态所以复杂度$O(3^{n})$
但他其实类似高维前缀和，于是可以$O(2^{n}*n)$
答案就是$\sum_{s,|s|=k} ans[s]$
总复杂度是$\sum_{i=0}^{s} cnt[s-i]^{3}$ , 其中$s=2^{n}-1$,$cnt[s]$ 表示二进制数 $s$ 中 $1$ 的个数
当$n=10$时，这个值为$166400$
但我也不会算，就当它是$O(2^{n}*n^3)$吧
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
char c;
while(gc<'-');
if(c=='-')
{
int x=gc-'0';
while(gc>='0')x=x*10+c-'0';
return -x;
}
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
template <typename T> void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
struct vec
{
int *a,n;
void pb(int x)
{
if(n==(n&-n))
{
int *_a=new int [n*2];
memcpy(_a,a,n*sizeof(int));
a=_a;
}
a[n++]=x;
}
};
const int N=10,U=1<<N;
int lk[N][N];
ll f[U];
int q[N];
ll qa[N][N],*a[N];
ll gauss(int m)
{
ll ans=1;
for(int i=0;i<m;++i)
{
for(int j=i+1;j<m;++j)
{
while(a[j][i])
{
ll bi=a[i][i]/a[j][i];
for(int k=i;k<m;++k)
a[i][k]-=a[j][k]*bi;
swap(a[i],a[j]);
ans=-ans;
}
}
ans*=a[i][i];
}
return ans;
}
int main()
{
freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
for(int i=0;i<N;++i)a[i]=qa[i];
int n=read(),m=read(),k=read();
while(m--)
{
int x=read()-1,y=read()-1;
++lk[x][y];++lk[y][x];
}
int u=(1<<n)-1;
for(int s=1;s<u;++s)
{
ll ans=1;
m=0;
for(int i=0;i<n;++i)
if(!(s&(1<<i))) q[m++]=i;
for(int i=0;i<n;++i)
if(s&(1<<i))
{
int cnt=0;
for(int j=0;j<m;++j) cnt+=lk[i][q[j]];
ans*=cnt;
}
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
a[i][j]=0;
for(int i=0;i<m;++i)
for(int j=0;j<i;++j)
{
int w=lk[q[i]][q[j]];
a[i][i]+=w;
a[j][j]+=w;
a[i][j]=a[j][i]=-w;
}
ans*=gauss(m-1);
if((n-m-k)%2==1) f[s]=-ans;
else f[s]=ans;
}
for(int i=0;i<n;++i)
for(int s=0;s<u;++s)
if( (s&(1<<i))==0 ) f[s]+=f[s+(1<<i)];
ll ans=0;
for(int s=0;s<u;++s)
{
int cnt=0;
for(int i=0;i<n;++i)
if(s&(1<<i))++cnt;
if(cnt==k)ans+=f[s];
}
cout<<ans;
}没有题解我来发一个。(同时来存模板)
http://acm.fzu.edu.cn/problem.php?pid=2246
第1种情况，t直接出现在s中。
那么要么割前面要么割后面。
求出t在s中第一次出现的位置和最后一次出现的位置即可。
第2种情况，t分成两半出现在s中。
那么枚举被分成哪两半，求出前缀在s中第一次出现的位置和后缀在s中最后一次出现的位置即可。
要求m个串的所有前缀在s中第一次出现的位置，建ac自动机，让s跑一遍就好了。
后缀的话全反过来做一遍就好了。
要注意: ac自动机中fail[i]不一定<i, 但深度顺序或者bfs序一定<i。(因为是i的后缀)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid (l+r>>1)
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
template <typename T> inline void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
#define gc (c=getchar())
int read()
{
char c;
while(gc<'-');
if(c=='-')
{
int x=gc-'0';
while(gc>='0')x=x*10+c-'0';
return -x;
}
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
struct vec
{
int *a,n;
void pb(int x)
{
if((n&-n)==n)
{
int *_a=new int [n*2];
memcpy(_a,a,n*sizeof(int));
a=_a;
}
a[n++]=x;
}
};
#define fore(arr) for(int *it=arr.a,*end=arr.a+arr.n;it!=end;++it)
const int N=1e5+500;
char s[N],T[N*2];int mn1[N*2],mn2[N],t[N],len[N];
int fail[N],ch[N][26],mn[N];int tot;
void ins(char *s)
{
int i=1;
for(char *c=s;*c>'0';++c)
{
int &to=ch[i][*c-'a'];
i=to?to:(to=++tot);
}
}
int q[N],tail;
void init_fail()
{
tail=1;q[1]=1;
for(int head=1;head<=tail;++head)
{
int i=q[head];
int f=fail[i];
rep(j,0,26-1)
if(ch[i][j]) fail[q[++tail]=ch[i][j]]=ch[f][j];
else ch[i][j]=ch[f][j];
}
}
void travel(char *s)
{
memset(mn+1,1<<5,tot*sizeof(int));
int i=1,l=0;
for(char *c=s;*c>'0';++c,++l) chmin(mn[i=ch[i][*c-'a']],l);
for(int i=tot;i;--i) chmin(mn[fail[q[i]]],mn[q[i]]);
}
void Get(int *f,char *s)
{
int i=1,l=0;
for(char *c=s;*c>'0';++c,++l)
{
i=ch[i][*c-'a'];
f[l]=mn[i];
}
}
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int tt=read();
rep(j,0,25)ch[0][j]=1;
while(tt--)
{
scanf("%s",s);
int n=strlen(s);
memset(ch+1,0,tot*sizeof(*ch));
tot=1;
int m;
cin>>m;
int nt=0;
rep(i,1,m)
{
scanf("%s",T+(t[i]=nt));
len[i]=strlen(T+nt);
ins(T+nt);
nt+=len[i]+1;
}
init_fail();
travel(s);
rep(i,1,m)
{
Get(mn1+t[i],T+t[i]);
}
reverse(s,s+n);
rep(i,1,m) reverse(T+t[i],T+t[i]+len[i]);
memset(ch+1,0,tot*sizeof(*ch));
tot=1;
rep(i,1,m) ins(T+t[i]);
init_fail();
travel(s);
rep(i,1,m)
{
Get(mn2,T+t[i]);
int l=len[i],*mn=mn1+t[i];
int ans=max(n-1-mn[l-1],n-1-mn2[l-1]);
rep(j,1,l-1)
chmax(ans, n-(mn[j-1]+1+mn2[l-1-j]+1) );
if(ans<0) puts("-1");
else printf("%d\n",ans);
}
}
}先考虑 $x^a=y^b$ 意味着什么
记 $p(x)$ 为最小的 $p$, 使得 $\exists k , p^k=x$。 那么 $x^a=p(x)^{k(x) \times a}$
则 $ x^a=y^b $ 等价于 $ p(x)^{k(x) \times a}=p(y)^{k(y) \times b}$ 等价于 $ p(x) = p(y) \land k(x) \times a = k(y) \times b $
考虑枚举 $p$ ，计算所有 $p(x)=p$ 的 $x$ 带来的重复
那么 使 $x$ 在给定区间 的 $k(x)$ 在一个区间中
于是问题转化为，求 $ card \{ i \times j \, | \, i \in [l_1,r_1] \, , j \in [l_2,r_2] \} $其中$l_1$,$r_1$为$O(log_2(n))$级别，$l_2$,$r_2$为 $O(n)$ 级别
容斥。
先加上在 $[l_1,r_1]$ 中任选一个数,并在 $[l_2,r_2]$ 任选一个数的方案数
再减去在 $[l_1,r_1]$ 任选两个数 $x,y$，并在 $[l_2,r_2]$ 任选两个数 $a,b$ ,使得$x \times a=y \times b$的方案数
再加上在 $[l_1,r_1]$ 任选三个数 $x,y,z$，并在 $[l_2,r_2]$ 任选三个数 $a,b,c$ ,使得$x \times a=y \times b=z \times c$的方案数 ......
可以发现 当 $[l_1,r_1]$ 中的数确定之后, $[l_2,r_2]$ 的方案数是可以算出来的 因为乘积一定为 $lcm$ 的倍数
设为 $x$ 倍 则$l_2 \le x \times lcm/max \, \& \& \, x \times lcm/min \le r_2$ 于是 $l_2 \times max \le x \times lcm \le r_2 \times min$
所以 $x$ 的取值数=$r_2 \times min/lcm - l_2 \times max/lcm +1$
于是暴力容斥复杂度 $=O(2^{r_1-l_1+1})=O(n)$
$l_1$,$r_1$一共有 $ log_2^2(n) $种
对于所有的一样的$l_1$,我们可以从小到大枚举$r_1$计算。 总复杂度还是 $O(n)$
当然还过不了
注意到 如果一个数选了之后对于$lcm,max,min$没有影响 那么他选和不选的贡献就会抵消
所以先枚举$max,min$ 之后$dfs$ 如果碰到对$lcm$无贡献的数，就直接退出
同时，如果选了它导致前面的数成为对$lcm$无贡献的数，那么它就不选
这样优化之后复杂度就很好了 李陶冶说"比较接近于光滑数的数量（其实比这个还要低一个数量级）"
但我不知道光滑数是什么东西 总之O(跑的过)
还有个问题，就是如何求出有多少个$p(x)$会使得$k(x)$在 $[l_1,r_1]$ 中
我是筛出$ \sqrt{n} $以内所有$p(x)=x$的$x$ 然后枚举 求更优的方法？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int D=1e9+7,Lo=52;
int cnt[Lo+2][Lo+2];
ll L1,R1,l2,r2,ans,now;
void init()
{
ll m,n,a,b;
cin>>m>>n>>a>>b;
ans=(m%D)*(n%D)%D;
L1=a;R1=a+n-1;l2=b;r2=b+m-1;
}
int Gcd[Lo+2][Lo+2];
int gcd(int x,int y)
{
while(y)swap(x%=y,y);
return x;
}
int l1,r1,mn;
ll L,R;//L(=l2*mx)<=x*Lcm<=R(=r2*mn)
int mx_p[Lo+5],st[Lo+5],*top;
#define len (R/Lcm - (L+Lcm-1)/Lcm +1)
void dfs(int *h,const ll &Lcm,bool ji)
{
if(Lcm>R)return ;
if(h>top)
{
if(ji)now-=len;
else now+=len;
return ;
}
int x=*h;
if(Lcm%x==0) return ;
//if(len<=0) return ;
dfs(h+1,Lcm,ji);
dfs(h+1,Lcm*(x/Gcd[x][Lcm%x]),ji^1);
}
const int U=8e7;
bool mark[U];
int main()
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
init();
int mp=sqrt(R1);
for(int p=2;p<=mp;++p)
if(!mark[p])
{
int k=0;
ll x=1;
while(x<L1&&x<=R1/p) { x*=p;if(x<=mp)mark[x]=1;++k; }
if(x<L1||x>R1)continue;
int l1=k;
while(x<=R1/p) { x*=p;if(x<=mp)mark[x]=1;++k; }
if(k>l1)
++cnt[l1][k];
}
for(int i=1;i<=Lo;++i)
for(int j=0;j<i;++j)
Gcd[i][j]=gcd(i,j);
for(int i=1;i<=Lo;++i)
for(int j=1;j<i;++j)
if(i%j==0) mx_p[i]=j;
for(l1=1;l1<=Lo;++l1)
{
int mr=0;
for(r1=Lo;r1>l1;--r1)
if(cnt[l1][r1]){mr=r1;break;}
now=0;
for(r1=l1+1;r1<=mr;++r1)
{
L=l2*r1;
for(mn=l1;mn<r1;++mn)
{
R=r2*mn;
if(L>R)continue;
int Lcm=r1*(mn/gcd(r1,mn));
int i=mn+1;
for(;i<r1;++i)
if(Lcm%i==0) break;
if(i<r1)continue;
top=st-1;
for(int i=mn+1;i<r1;++i)
if(mx_p[i]<=mn)
*++top=i;
dfs(st,Lcm,0);
}
now%=D;
ans-=cnt[l1][r1]*now%D;
}
}
cout<<(ans%D+D)%D;
}先在线段树上二分得到 满足子树点权和>=总点权/2的 dfs序最大的点x
之后再考虑计算带权距离和，即 $ans(x)= \sum_{i} dis(i,x) * v[i]$
因为$dis(i,x)=deep[i]+deep[x]-2*deep[lca]$
所以$ans(x)=(\sum_{i} deep[i] * v[i]) + (deep[x]*\sum_{i} v[i]) -2*(\sum_{i} v[i]*deep[lca]) $
前两项直接维护
最后一个式子怎么算呢
就是每次 $v[i]$+=$x$ 就把$i$到根的路径上的点的$add$全部+=$x$
查询$ans(x)$时 就查询x到根的$\sum_{i} add[i]*(deep[i]-deep[fa[i]])$
线段树预处理区间$\sum_{i}(deep[i]-deep[fa[i]])$后可以维护
时间$O(nlog^2)$ 跑的还是挺快的
# pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pb push_back
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
int read()
{
while(*++now_r<'-');
if(*now_r=='-')
{
int x=*++now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return -x;
}
int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
void write(ll x)
{
static char st[20];static int top;
if(!x)*++now_w='0';
else
{
do{st[++top]='0'+x%10;}while(x/=10);
do{*++now_w=st[top];}while(--top);
}
*++now_w='\n';
}
const int N=1e5+5,T=N*4;
struct edge
{
int to,w;
};
int n,m;
vector<edge>lk[N];
int fa[N],deep[N],sz[N],son[N],top[N],dfn[N],tot;
int q[N];
void dfs(int x,int fr,int dep)
{
fa[x]=fr;deep[x]=dep;sz[x]=1;
vector<edge>::iterator i=lk[x].begin();
while(i!=lk[x].end())
{
int y=i->to;
if(y==fr){++i;continue;}
dfs(y,x,dep+i->w);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])son[x]=y;
++i;
}
}
void dfs2(int x,int ntop)
{
q[dfn[x]=++tot]=x;top[x]=ntop;
if(!son[x])return ;
dfs2(son[x],ntop);
for(vector<edge>::iterator i=lk[x].begin();i!=lk[x].end();++i)
{
int y=i->to;
if(y==son[x]||y==fa[x])continue;
dfs2(y,y);
}
}
int x,w;
ll xs,s;
#define mid (l+r>>1)
#define cl (k*2)
#define cr (cl+1)
namespace seg
{
int ad[T],mx[T];ll s[T],xs[T];
int ql,qr;
inline void _add(int k,int x)
{
ad[k]+=x;mx[k]+=x;
xs[k]+=s[k]*x;
}
inline void down(int k)
{
if(ad[k]){_add(cl,ad[k]);_add(cr,ad[k]);ad[k]=0;}
}
inline void up(int k)
{
mx[k]=max(mx[cl],mx[cr]);
xs[k]=xs[cl]+xs[cr];
}
void add(int k,int l,int r)
{
if(ql<=l&&qr>=r){_add(k,w);return ;}
down(k);
if(ql<=mid)add(cl,l,mid);
if(qr>mid)add(cr,mid+1,r);
up(k);
}
void add(int l,int r)
{
ql=l;qr=r;
add(1,1,n);
}
void init(int k,int l,int r)
{
if(l==r)
{
s[k]=deep[q[l]]-deep[fa[q[l]]];
return ;
}
init(cl,l,mid);init(cr,mid+1,r);
s[k]=s[cl]+s[cr];
}
int qiu(const ll &x)
{
int k=1,l=1,r=n;
while(l!=r)
{
down(k);
if(mx[cr]>=x) {k=cr;l=mid+1;}
else {k=cl;r=mid;}
}
return l;
}
ll ans;
void qiu(int k,int l,int r)
{
if(ql<=l&&qr>=r){ans+=xs[k];return ;}
down(k);
if(ql<=mid)qiu(cl,l,mid);
if(qr>mid)qiu(cr,mid+1,r);
}
ll qiu(int l,int r)
{
ql=l;qr=r;ans=0;
qiu(1,1,n);
return ans;
}
};
void add_to_rt(int x)
{
while(x)
{
int f=top[x];
seg::add(dfn[f],dfn[x]);
x=fa[f];
}
}
ll qiu_s(int x)
{
ll ans=0;
while(x)
{
int f=top[x];
ans+=seg::qiu(dfn[f],dfn[x]);
x=fa[f];
}
return ans;
}
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
fread(ch,1,ch_top,stdin);
n=read();m=read();
rep(i,1,n-1)
{
int a=read(),b=read(),c=read();
lk[a].pb((edge){b,c});lk[b].pb((edge){a,c});
}
dfs(1,0,0);
dfs2(1,1);
seg::init(1,1,n);
while(m--)
{
x=read();w=read();
add_to_rt(x);
xs+=(ll)deep[x]*w;
s+=w;
x=q[seg::qiu(s+1>>1)];
write(xs+s*deep[x]-2*qiu_s(x));
}
fwrite(ch,1,now_w-ch+1,stdout);
}
鄂公网安备 42010202000505 号Server time: 2024-04-20 14:39:31