题目描述

invisibleassassin是一个Archer，非常擅长射箭(Gate of Babylon)。

今天invisibleassassin的练习是要射一棵树。一棵树是一个 \(n\) 个点 \(n - 1\) 条边的无向图，且这棵树的第 \(i\) 个点有一个值 \(w_i\)。

每一次invisibleassassin会射中树的一条边，并将这条边移除。

此外，invisibleassassin定义一棵树的las 值为 \(Σv_i * i\) ，\(v_i\) 为这棵树中第 \(i\) 小的 \(w_i\) 。

现在invisibleassassin会告诉你她射中的边的顺序，你需要回答每一次她射中的边所在的树的las 值，之后被射中的边会被移除。

答案mod 998244353。

输入格式

第一行两个数 \(n,m\)

第二行 \(n\) 个数 \(w_i\)

接下来 \(n-1\) 行每行两个数 \(a_i,b_i\), 表示初始的树第 \(i\) 条边连接 \(a_i\) 和 \(b_i\)。

接下来 \(n-1\) 行每行一个数表示射中的边。

输出格式

\(n - 1\) 行，每行一个数表示射中的边的树的las 值

样例数据

input

5 4396
2 3 1 4 5
1 2
1 3
2 4
2 5
4
1
2
3
7

output

55
30
5
11

数据规模与约定

前20% \(n\leq 10^{3}\)

另外20% \(m\leq 10\)

另外20% 保证第 \(i\) 条边连接 \(i\) 和 \(i + 1\)

另外20% \(n\leq 10^{5}\)

100% \(n\leq 5*10^5,1\leq w_i\leq m\leq 10_4\)

时间限制：\(1\text{s}\)

空间限制：\(512\text{MB}\)

Solution

首先，树上断边的套路，倒过来加边。每次加边就想到与合并两棵树，那么自然想到线段树合并。想到线段树合并那么这道题也就A掉了。下面就是套路的东西了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define REP(i,a,n) for(register int i=(a);i<=(n);++i)
#define PER(i,a,n) for(register int i=(a);i>=(n);--i)
#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)
template<typename A>inline void read(A&a){a=0;char c=0;int f=1;while(c<'0'||c>'9')(c=getchar())=='-'?f=-1:0;while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();f==-1?a=-a:0;}
char buf[30];template<typename A>inline void write(A a){if(a<0)putchar('-'),a=-a;int top=0;if(!a)buf[top=1]='0';while(a)buf[++top]=a%10+'0',a/=10;while(top)putchar(buf[top--]);}
typedef long long ll;typedef unsigned long long ull;
template<typename A,typename B>inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;}
template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}

const int N=5e5+7,M=1e4+7,MOD=998244353;
ll n,m,w[N],x,y,p[N],ans[N],ac,Ans[N],STD;
struct Graph{int x,y;}G[N];

struct Node{int lc,rc;ll sum,val;}t[N*20];int RT[N],nod;
inline void Insert(int &o,int L,int R,int x,int k){if(!o)o=++nod;t[o].val+=k;(t[o].sum+=((ll)k*x%MOD))%=MOD;if(L==R)return;int M=(L+R)>>1;x<=M?Insert(t[o].lc,L,M,x,k):Insert(t[o].rc,M+1,R,x,k);}
inline void Merge(int &o,int o2){if(!o||!o2)o^=o2;else{if(!t[o].lc&&!t[o].rc&&!t[o2].lc&&!t[o2].rc)(ac+=(ll)t[o].val*t[o2].sum%MOD)%=MOD;else ac=(ac+(ll)t[t[o2].lc].val*t[t[o].rc].sum%MOD)%MOD,ac=(ac+(ll)t[t[o].lc].val*t[t[o2].rc].sum%MOD)%MOD,Merge(t[o].lc,t[o2].lc),Merge(t[o].rc,t[o2].rc);t[o].val+=t[o2].val,(t[o].sum+=t[o2].sum)%=MOD;}}
//错误笔记：上一行的Merge中一样的数也要算排名！！！！ 
int fa[N];
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
inline void Union(int x,int y){x=Find(x),y=Find(y);x==y?0:fa[y]=x;}

int main(){
    read(n),read(m);
    for(register int i=1;i<=n;++i)read(w[i]),Insert(RT[i],1,m,w[i],1),ans[i]=w[i]*1,fa[i]=i;
    for(register int i=1;i<n;++i)read(G[i].x),read(G[i].y);
    for(register int i=1;i<n;++i)read(p[i]);
    for(register int i=n-1;i;--i){
        x=Find(G[p[i]].x),y=Find(G[p[i]].y);STD=i;
        ans[x]+=ans[y];ac=0;Merge(RT[x],RT[y]);(ans[x]+=ac)%=MOD;Union(x,y);Ans[i]=ans[x];
    }
    for(register int i=1;i<n;++i)write(Ans[i]),putchar('\n');
}

[校内NOIP2018模拟20181020] wph World Final 捧杯稳

原文：https://www.cnblogs.com/hankeke/p/20181020-las.html