本文共 3664 字，大约阅读时间需要 12 分钟。
1 #include 2 //#pragma comment(linker, "/STACK:1024000000,1024000000") 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 using namespace std; // 16 17 #define ll long long 18 #define ull unsigned long long 19 #define pb push_back 20 #define FOR(a) for(int i=1;i<=a;i++) 21 #define sqr(a) (a)*(a) 22 #define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)) 23 ll qp(ll a,ll b,ll mod){ 24 ll t=1;while(b){ if(b&1)t=t*a%mod;b>>=1;a=a*a%mod;}return t; 25 } 26 struct DOT{ll x;ll y;}; 27 inline void read(int &x){ int k=0;char f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())k=k*10+c-'0';x=k*f;} 28 const int dx[4]={ 0,0,-1,1}; 29 const int dy[4]={ 1,-1,0,0}; 30 const int inf=0x3f3f3f3f; 31 const ll Linf=0x3f3f3f3f3f3f3f3f; 32 const ll mod=1e9+7;; 33 34 const int maxn=2e5+9; 35 36 int n; 37 38 struct EDGE{ 39 int v;int w;int next; 40 }G[maxn<<2]; 41 int head[maxn],tot; 42 43 inline void addedge(int u,int v,int w){ 44 ++tot;G[tot].v=v;G[tot].next=head[u];G[tot].w=w;head[u]=tot; 45 } 46 47 /* 48 int top[maxn]; 49 int pre[maxn]; 50 int dep[maxn]; 51 int num[maxn]; //子树尺寸 52 int p[maxn]; //v的对应位置 53 int out[maxn]; //退出时间戳 54 int fp[maxn]; //访问序列 55 int son[maxn]; //重儿子 56 int pos; //计时器 57 */ 58 inline void init(){ 59 memset(head,-1,sizeof head);tot=0; 60 //memset(son,-1,sizeof son); 61 } 62 /* 63 inline void dfs1(int u,int fa,int d){ 64 dep[u]=d; 65 pre[u]=fa; 66 num[u]=1; 67 for(int i=head[u];~i;i=G[i].next){ 68 int v=G[i].v; 69 if(v==fa)continue; 70 dfs1(v,u,d+G[i].w); 71 num[u]+=num[v]; 72 if(son[u]==-1||num[v]>num[son[u]])son[u]=v; 73 } 74 } 75 inline void getpos(int u,int sp){ 76 top[u]=sp; 77 p[u]=out[u]=++pos; 78 79 fp[p[u]]=u; 80 if(son[u]==-1)return; 81 getpos(son[u],sp); 82 for(int i=head[u];~i;i=G[i].next){ 83 int v=G[i].v; 84 if(v!=son[u]&&v!=pre[u])getpos(v,v); 85 } 86 out[u]=pos; 87 } 88 */ 89 ll add[maxn]; 90 int a[maxn]; 91 92 /* 93 struct NODE{ 94 int l,r; 95 ll sum; 96 ll add; 97 }ST[maxn<<2]; 98 inline void pushup(int rt){ 99 ST[rt].sum=ST[rt<<1].sum+ST[rt<<1|1].sum;100 }101 inline void pushdown(int rt){102 if(ST[rt].add){103 ST[rt<<1].sum+=ST[rt].add*(ST[rt<<1].r-ST[rt<<1].l+1);104 ST[rt<<1|1].sum+=ST[rt].add*(ST[rt<<1|1].r-ST[rt<<1|1].l+1);105 ST[rt<<1].add+=ST[rt].add;106 ST[rt<<1|1].add+=ST[rt].add;107 ST[rt].add=0;108 }109 }110 inline void build(int l,int r,int rt){111 if(l==r){ST[rt].l=ST[rt].r=l;ST[rt].sum=0;return;}112 ST[rt].l=l;ST[rt].r=r;113 int m=l+r>>1;114 build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);115 }116 inline void update(int a,int b,int c,int l,int r,int rt){117 if(a<=l&&b>=r){118 ST[rt].sum+=(r-l+1)*c;119 ST[rt].add+=c;120 return;121 }122 int m=l+r>>1;123 pushdown(rt);124 if(a<=m)update(a,b,c,l,m,rt<<1);125 if(b> m)update(a,b,c,m+1,r,rt<<1|1);126 pushup(rt);127 }128 inline ll query(int x,int l,int r,int rt){129 if(l==r){return ST[rt].sum;}130 int m=l+r>>1;131 pushdown(rt);132 if(x<=m)return query(x,l,m,rt<<1);133 else return query(x,m+1,r,rt<<1|1);134 }135 136 inline void solve(int u,int v){137 138 while(top[u]!=top[v]){139 140 if(dep[top[u]] =0;j--){194 if(falen[now][j] <= a[i]){195 a[i]-=falen[now][j];196 now=fa[now][j];197 }198 }199 200 if(i==now)continue;201 add[fa[i][0]]++;add[fa[now][0]]--;202 }203 dfs(1);204 for(int i=1;i<=n;i++)printf("%lld ",add[i]);205 //for(int i=1;i<=n;i++)printf("%lld ",query(p[i],1,n,1));206 207 }
转载于:https://www.cnblogs.com/Drenight/p/9123864.html
